Check Craig's list. A lot of people buy a new bike every year or two and can because they sale or trade in there old bikes. Also, if you look for family business type bike shops, you can often find great deals if your willing to put in some time, work and a little money to get the bike up to speed. Just look around their 'bike graveyard'.
I have a 96 mtn. bike and a mid 80's road bike and I love them both and both are a heck of a lot better than any bike you can find at walmart. You don't need something fancy to enjoy the bike, just make sure it's quality and won't fall apart. Trek, Giant, Gary Fisher, and Specialized come to mind for mtn. bikes. I'm really not to familiar with road bikes. Maybe Bird can chime in.
On Craig's list, my brother found a Specialized model from a couple years ago for half the price you would in a bike shop. Granted he still shelled out a grand lol. Good luck.