There is no way a frontier gets 19 MPG city with my definition of what city is (not even a 4 banger)... in fact, it has difficulty getting 19 on 100% highway. I think you are looking at your gauge, which is obviously wrong.
Well according to my definition of city, its possible. If I drive like a nut, which is what I usually do, I get about 17-18. If I'm light on the gas, I'll get about 19, maybe 20. Thats here in Lubbock where we have no hills and I get on the freeway maybe once a week for about 2 miles, everything else is surface streets.
19 on 100% highway IS what I get when I keep it between 75 and 80. If I slow down to 70 I get 21-22, depending mostly on wind conditions.
I'm at about 40,000 miles on the odometer with 265/75/16 tires.
As far as the OP goes, I think I wouldn't worry about it till after your first oil change. It still needs to be broken in, and even if your milage doesn't improve, you've still got a lot of warranty left to get it taken care of.