I'm going to get shredded by the bikers here but hey, what the heck. I also bike a lot. These days I only mountain bike because I find it more enjoyable. I also rather get hit by a tree than a car.
Folks that road bike a lot will tell you the first thing to do is to get fit for a bike. That's fine but you could dish out a few hundred bucks for that luxury. Bikes have been around for a long time. Not sure for how long but I will venture to guess since the late 1800's. Millions and millions of us have managed to ride without getting fitted. You have a tight budget and you are going to do it for exercise. Maybe down the road you will want to go all in. But for now, a reliable bike is what you need. This is not rocket science. Sit on a horrible seat, put your feet on the pedal, grab the bars and go.
You will be looking for something that falls into the entry mountain bike category. Do not get a hybrid. They suck for off road use. I think you will want to limit your choices to a rigid (no suspension) or hardtail (front suspension). Suspension adds to the price. At your price point full suspension is out. Anything you would get would be crap. Good full suspension gets expensive. If your trail riding is basically fire roads or smooth, you can get away with a rigid. However, some front suspension will make it much more comfortable and really open up where you can ride. I rode a hardtail for a while and hit some very bony trails when I lived in New England. Even hit some small drops with it.
Get a feel for the size bike you will need. It is easy to figure out, just do a little reading. A little smaller is better than a little bigger. You can buy a cheap stem of different lengths down the road to tweak your fit if you desire, but honestly it won't matter. A dedicated road bike is a bit different, because you are hunched over for long periods. Trail riding, you are always changing your position, which does a lot to improve your comfort.
Check out bikesdirect.com. Lot of bang for your buck there and they tend to have way better specs then the big guys at the same price points. Don't get caught up in the weight game and the latest and greatest in frame tech. Unless you are a racer, a 34 pound bike is just as much fun as 28 pound bike. Less weight adds a lot to cost. It is all about getting the best components you can afford. Especially if you go off road. Cheap components go out of whack all the time. The middle of the road stuff by Sram and Shimano are very good. Same goes for your front fork, if you go that route. Do some reading so you know what is good and what is junk. Good suspension makes a world of difference.
I started on a $500 mountain bike. Today I am on a $5,000 bike. I had as much fun on the $500 bike as I do on my current ride. It's all good. Is my new bike better? Yup. But I'm 54 years old and I need all the cush I can get