Should I use Python or PHP? (I'm leaning towards Python)
Use what you know best.
Should I use Django, Pyramid, Flask, or something else as the framework? (I'm leaning towards Django)
Use what you know best. I personally prefer Flask.
Should I buy hosting, use Google App engine, or get a dedicated server?
Google App Engine is rather pricey and has a lot of lock-in. Have you considered something like DigitalOcean or WebFaction?
How will I store data, how will users login (Open ID, or should I create a login service).
OpenID is pretty much dead if you ask me. Use Persona instead. Sample Persona log-in code for Flask and PHP: https://github.com/workhere-io/personaexamples
How will things scale if the app performs well?
Upgrade your VPS. Flask + PostgreSQL can take quite a couple of hits.