I have been where you are, the time i decided to buy 4x4 , and since I am not a big fan of american cars specially, Jeep. My choices according to my budget became limited to FJ and Xterra ..
So Why I chose FJ over Xterra...
Forget about the coolness and horsepower , which is every superficial point of argument ...
You wanna be a true adventure and be taken series , you will definitely choose FJ...
You need a car that has adventurous spirit as you are...
I donot think a true adventurer would love to go off-road with a car that has saloon car like interiors , and when I say off-road does not mean only the sands ... It means also to wadi and mountains in Oman and UAE.. you need interiors that looks great when it's dirty and does not make you feel like you fucked up your city car too...
FJ interior are not only very practical when it comes to this point but it's also spacious , which is another thing you will learn with your first long weekend offroad trip, when realise that you just can't keep everything in place in a long trip ...
Those who say that Xterra is more manly.. I can't see your point... because once you step into FJ you feel like you stepped into a tank ,, a feeling you will never have when you get into Xterra... and when you press on the gas pedal and hear the engine with the face of the car lifts up by the engine power , you gotta excuse Fj guys for being so cocky ...
Both cars are capable off-road , but a true adventurer and off-roader knows it's the driver that makes difference all the time , but when off-roading get a little bit serious Xterra guys usually quit , why ? because you gotta do some modifications and you need car that gets the after market attention... FJ has an after market part for every essential off-road component, you can change side steps and bumpers and replace skid plates with many options available ... obviously the suspension with different grades are available too ...
if you choose Xterra I won't Judge you, but I think you have decided already when you are going to quit offroading...