To expand on my earlier comment since I now have a actual keyboard...
I started out with a Samurai that I traded a enclosed trailer for. Build thread Here. Lots of lift. Locked diffs. 33" tires. Winch. Tire carrier. The works. It was literally unstoppable. I've never gotten it stuck.
It sucked to drive on the street. And unless all your wheeling is going to be in one place, you need a streetable vehicle that is capable off road. Enter Samurai 2.0. 2" of lift. 30" AT tires. No tire carrier. A 100% more usable vehicle for the off road exploring I do. It still hasn't been stuck. I don't go through what I can go around. Still really only usable as a local rig. At 70 it's not a lot of fun to drive. If you want to go any serious distance, you are going to want to flat tow it. Also, no A/C in the south kills it for anything other than a 3 season rig. As it sits now. I still love the little thing and it's a vehicle I'll probably never sell.
In the search for something a little nicer to drive I came up with this. A 2000 Cherokee. Build thread Here It has a few creature comforts the Samurai was lacking. Notably, A/C, cruise control, and power steering. I bought a pretty nice one instead of a beater and it set me back about $3500.
In preparation for some trips I want to make over the next couple of years it now looks like this. I learned my lessons on the Samurai. It is very capable and still drives very well down the interstate at 75 with the cruise set and the A/C on full blast.
You probably need to start with considering what kind of off roading you want to do. Rock crawling demands a completely different vehicle compared to sightseeing or camping is at the end of a dirt road. The Trans American Trail is going to require a different vehicle than mud bogging. Spend some time on YouTube and see what appeals to you and go from there.
You can pick up a XJ on 33s with 6" of lift for pretty cheap. You won't want to drive it 500 miles to the mountains to explore forest service roads though. If you want to go run the Kentucky Adventure Tour, a Rav4 probably won't make it and a full size truck it going to get scratched to hell and back. There are also some places a full size vehicle just won't go.
I picked the XJ for it's size, availability of parts anywhere in North America, inexpensive aftermarket and parts support. For instance, the winch bumper for my XJ was $150. A winch bumper for my son's Xterra is $600. Do some research and see what fits your needs and budget.
Edit to add: My son blew up the above mentioned Xterra. A rebuilt engine was $3500 and working on that thing was a pain. In the year he owned it I had to retrieve it from the side of the road 4 times for assorted issues. He bought the green XJ in my first post, added a 2" lift, 5 - 31x10.5x15 tires, replaced a bent tie rod, and replaced the oil pan gasket for under $2500.