I pull with a Pathfinder, which is just the SUV version of your Frontier. We tow a 4000 lbs Jayco x23B, with roughly another 500lbs of people and stuff (the kids are still small), and it's "adequate" but is not a great tow vehicle. Mostly it's fine to tow around the flats of Illinois, but towing through the Black Hills last summer, it was a lot of 3rd gear, 3500-rpm towing while getting 7-8 mpg. That 20-gallon tank does look awfully small with those numbers--we stopped every 100-150 miles to fill up. The tongue limit is 600lbs, so you're looking at relatively light trailers. It gets the job done, but if you can afford a bigger truck, that would be the way to go.
