Check all the stuff mentioned above, but just because a relay is clicking doesn't always mean it's good. They could test fine (pass continuity tests and possibly pass voltage drop tests) and fail under load. I've disassembled failed relays in the past to see why they failed and they've had burnt contacts and / or broken parts. If you remove it and shake it and hear loose parts, those parts might cause a short as described above.
You said both headlights went out at the same time - In the diagram above, both are :
1. Powered by the same fusible link.
2. Powered by the same relay.
3. Share the same grounds.
4. Go through the same headlight switch.
The fusible link likely powers other things as well, have you tested those other items?
If everything above is checked and good, then I'd look for a chaffed / melted wire that's shorting somewhere.
Also, this is likely not the issue but since you're in there, now is a great time not just to check & clean grounds, but to add grounds if needed.
Please post pics of what you find.