I use Staples Photo paper. They've changed it to Gloss paper or something; I think it's in a purple envelop now. I'm not certain. I have a stack of the old stuff.
I think if you are starting out, the Pulsar paper is a good deal. If you want to move to cheaper alternatives later you can.
Double siding and other details are all in older posts.
You can always change the pad sizes in the Eagle footprint libraries if it doesn't match your requirements for etching. I had to adjust a few of them for a boardhouse with 8mil trace/spacing limits.
Really, I don't have many chips that aren't QFP, QFN, or TSSOP, all with 0.5mm spacing. If I couldn't etch for them, I'd be screwed.
EDIT: Generally I can do smaller spacing than I can do traces, so for 0.5mm leads, I do 10mil traces and let the spacing suffer. I also find with 8mil traces, the copper can seperate from the board much easier, so you can get pads that break loose if you are a little hard on them.