Well, as Scott suggests, start with a price-point. You can easily spend over $5000 on a really really nice bike, but I would think that's not what you're going for.
However, $800 will get you a nice (not top-of-the-line, but decent) 21-speed hybrid that you can use for both road and crushed-limestone/gravel riding. If you're going to be doing lots of chunk gravel riding, I would suggest not getting "road slick" tires (like I use on my bike), but also not full-on heavy knobby tires. There are some "in between" tires that are not-great for either straight-road or straight-gravel riding, but decent for both.
My biggest suggestion here would be to go to a real bike shop, not your local SportMart, KMart, Wal-Mart, etc. Go to a place that sells bikes, and only bikes. You'll get the right attention paid to making sure that you're a good fit for your bike, and vice versa. The *-Mart stores don't know what they're doing when it comes to that. (Trust me, I'm still riding a bike purchased at SportMart, and I've got over 5,000 miles on it.)