I don't have any experience with PID loops. The concept doesn't seem too hard, but programming one sounds like it might be fairly complex.
I can help with your relay problem though:
For low current DC, you can use reed relays. They can typically handle switching loads of around 100mA.
The next step up is using a transistor of some sort. To get more gain you might need to use two transistors, or a transistor that switches a relay.
The easiest thing for switching AC power is a solid state relay. The arduino can switch them directly. I'm using one of these in my
attic heat project to power the fans.