I pondered the same decision: Mtn bike or road bike, I went with the road bike since most of my riding will be on pavement. However, if you're doing a mix, I would suggest a hardtail with a lockout front suspension or a rigid fork as Dirigible had suggested. Maybe put some slicker tires to get you where you want to go fast. I would definitely not go with a full suspension bike. They're horrible for pavement as you lose a lot of momentum due to the suspension.
Do your research on proper frame size before you go out and buy anything. Proper sizing is a must.
If you really want to go cheaper, buy an older Specialized Rockhopper. Older, but still killer bikes to have and build up.