I use T-Mobile whenever I am in the States for the last 3 years now and it always worked great for me. The have a 2G plan where you only pay 2$ per day and for me that was always sufficient for maps, email and a bit of browsing.
You can just walk into a T-Mobile store and they should have the nano SIMs.
AT&T does not allow iPhones with prepaid card on their network
This is partially false. They allow iPhones on prepaid but you won't get data with it.
EDGE connection for Maps is a pain in the a$$.