I just went through the design rules of just about every prototype PCB house I know of to determine what my design rules should be so I have complete freedom of choice.
I think the list is pretty well covered on the Adafruit cost calculator page, along with links there.
Almost all of them will do 4 layer boards. Of course, I can't design 4 layers on the free version of Eagle CAD.
Olimex has more restrictive rules than most. I'm noting where their rules are tighter in the list below.
1 oz copper on 0.062-inch FR4 is universal. No surprise. Only a couple in the list will do heavier copper.
7/7 mil minimum track width and spacing except Olimex at 10. I'm sticking with 10/10 except where SMT parts make it impossible. The boards are more likely to not have opens and shorts at those dimensions.
Minimum drill size is all over the place. 20 mil covers all except Olimex at 24. I happen to have my vias set at 24 mils.
Minimum annular ring around holes is often not specified. A couple require 5 mil, Olimex 8. I'm going with 10 mil (44 mil vias) for reliability and improved yields.
Max drill size is 246 mil or larger for most, but AP Circuits is 125 and Olimex is 195. Several of them won't do non-plated holes, and some will only do them with an extra charge.
Only Olimex specified copper and holes to board edge, and they used 20 mil. I have one board where I put the edges of some traces at 20 mil from the board edge, and it felt like I was putting them right on top of the edge of the board.. I like to leave 50 mil to traces and 100 mil to the centers of holes. If I am making boards at home, I know I will need that.
Minimum board size of 1.25"x1.25" covers them all. Many will go down to 0.5"x0.5". My smallest board is 1.0x0.9, eliminating Gold Phoenix (by 0.1 inch), PCB FAB Express, and Advanced Circuits.
Maximum board size is at least 10"x10" for all but Olimex (12.59x"x7.87" max) and Advanced Circuits "$33 each" deal at 60 sq in. Not an issue for me.
Overall, I could shave a few mils off of my boards with smaller vias, and a few more mils with smaller traces, but I'd pay a price in getting more PCBs with manufacturing defects.