cyclocross with disc brakes - I am biased. Bicycles can go from 300 to name your price. Less than 300 for a new bike and the quality and strength may be compromised. The cyclocross bikes go for around USD700 to USD1200 and upwards. Just remember that as a clyde the wheels, frame and saddle are the most important things.
Sorry for the terms below I'm assuming that you'll ask if you don't know what I mean (I sometimes don't know what I mean
I strongly recommend getting the wheels rebuilt by a good wheel builder as soon as you buy the bike. More, thicker spokes means a stronger wheel (for example try 36 spokes, stainless steel straight gauge 2.0, with brass nipples, laced 3 cross). A V-section rim with DOUBLE eyelets should be strong enough (for example try mavic CXP33 36 hole black anodised). Finally, the hub should have a wide flange to limit spoke breakage (my suggestion would be dtswiss 240s disc but they're an expensive hubset - any good quality hub with a relatively wide flange will do).
As long as the frame is good quality then you should have no problem with either steel or aluminI
um. I went with aluminI
um as I didn't want any rust headaches but a lot of the other guys here ride steel bikes with no problems.
There are a number of excellent saddle recommendation threads already, that is, saddle choice is purely an individual thing (it needs to fit your butt so what I find comfortable you may think is a brick).
For Cyclocross bikes with disc brakes try voodoo, redline, salsa, kona, opus, cannondale, mountaincycle, lemond, norco, zion, trek, etc
Anyway, hope there wasn't too much crap to sift through and I hope at least some of it helped.