A 2000-2004 came with a 265/70R16 (equivalent to a 30") stock, the Supercharged ones got a 75R16 (Equivalent to a 31"). The 2005+ came stock with a 265/70R17 (31") or a 265/75R17 on the Off-Road models.
If your budget allows it, I would recommend a 2005+ Off-Road. The Off-Road package adds a rear electric locking differential, as well as Bilstein shocks and skidplates underneath. It's Nissans equivalent to the TRD package on Tacomas and the FJ Cruiser. If that's not in the cards, try to find an 02-03 non-supercharged with the 4.9 gears. You can tell the gear ratio by looking at the vehicle information placard on the inside of the drivers door. The Axle Code should be HG49. The first gen Xterras also have a much stronger drivetrain than the 2005+. The rear end on the first gens is Nissans tried and true H233b--the ring gear is 9 3/4" in diameter, and it's simply indestructible. I know of at least three 2005+ Xterras and Frontiers that have blown the rear diffs, and countless that have blown up the front diffs. I only know of ONE 2000-2004 Xterra that has blown up a front diff, and I've never heard of anyone blowing up an H233b.
Yes, locker and gear options for the Nissan axles aren't very widespread, but there are ARB Air Lockers for the first gen Xterras. Gears are very expensive, and Nismo is the only company that makes them--up to 5.13.
The VG33, the 3.3L V6 in the first generation Xterras, might be a little bit anemic, but it is anything from weak. The VG block is the most durable and reliable motor that Nissan has ever produced, in E (SOHC 12V) or ER (SOHC Supercharged) format. The only "issue" with them is the timing belts, be sure that it's been changed if you're looking at a higher mileage (>100,000 miles) unit.
The 2005+ Xterras, and Frontiers come with a VQ40, a 4.0L 265HP V6. They are rated for higher towing, better fuel economy, and better performance overall, but the longevity of the motor has not yet been determined. I know of at least 10 VG block Pathfinders with well over 300,000 miles and going strong. If reliability is a primary concern, the first gen Xterra will definitely do you well.
I'll second the vote against a 3" Bodylift, because there are a lot of issues related to it. A 2" BL will allow you to run 32" tires without having to trim fender linings, and is relatively easy to install yourself. I've installed a few myself over the last couple of years, but I will not touch a 3". The First Gen X has a lot more "Budget" mods available than the Second Gen. The Poor Mans Lift, mentioned by XterraWolf, is one of them. It is simply a set of longer rear shackles for the leaf springs, and a crank of the torsion bars in front to yield about 2" of lift. Replacing the upper control arms with aftermarket units, will allow you to crank the T-bars to about 3" and retain factory alignment specs.
As far as armor goes, check out
Shrockworks for all of your Xterra protection needs. They're based out of Houston, TX and do phenomenal work, and I've heard nothing but great things about their customer service. AC is another good company to deal with for aftermarket Nissan bits.
Well...my fingers are getting tired, so if you have any more questions, just ask!