I'd personally skip out on the built in Nav. I haven't used the T4R's Nav, but a majority of OEM units are clunky in operation.

Thought about buying a Limited and swapping seats with someone? I'm sure there is someone localish that would be down for trading their TE seats for some limited leather seats.

I have 13k miles on my SR5 w/ premium package and the seats are holding up really well. I don't know if cloth or leather would be more prone to hold in fish smell. Part of the reason I went with leather was that I'm expecting there will be kid spit-up back there at some point and the leather should prevent the yuck from soaking into the seat foam.