Top end of both budget and quality would probably be Ingersol-Rand.
For home shop use, probably Porter Cable or Campbell Hausfield (actually, both pretty much the same, since they're both owned by the same parent company).
If you go the Sears (Craftsman) route, stay away from the oilless models and get a belt driven oil sump model.
You'll need a fairly large compressor & tank to do much paint spraying, although you can still do a fair amount with a 1.5 hp model with a 20 gallon tank. That's what I have, and I use mostly an HVLP 'touch-up' gun for most of my spraying, with good results.
For nailers, you don't need a big compressor. One of the 'pancakes' or 'hot dog' models is plenty. Senco, Paslode, and Hitachi all make high quality nailers, but for home use, Porter Cable, or even the (cheap!) Harbor Freight models work well.
If you intend to use air sanders, then you'll really need a big compressor. Sanders reallu use a lot of air - most are in the range of 9~12 CFM @ 90psi, and it taks a big compressor to keep up.
Probably more than you wanted to know, but there ya go!