What are my options for MVC, GUI + Interactive Visualization in App Engine (python)?
App Engine is flexible on the UI side. The Python supports Django templates (0.96 out of the box, and 1.2 with a one-line config change). Django templates are easy to use, and are JavaScript toolkit neutral. I use jQuery, but that's a personal choice that App Engine doesn't impose. On the UI side, it's a safe choice, and any time you put in to learning the Django template language and jQuery is portable beyond App Engine. I don't see a lot of pissing on Django, but maybe I'm hanging out in different places.
Though you emphasize the UI side, I'd look first at how to map your large graph on to the App Engine datastore, and how the queries against your graph will perform. The nuances of the App Engine datastore often trip up people who have a lot of relational experience and expect tables and real foreign keys. It's well-suited for storing graphs, but it's worth exploring and prototyping your queries, so that you know what you're getting in to.
The App Engine SDK is great for local (e.g., laptop in a coffee shop) development.
I'm a bit biased, though.
I'm creating an app that allows users to query, manipulate, and explore a very large graph.
What's the 'best' way to create a gui + visualization for my project?
By best I mean the following:
1. conforms to web standards, no flavor of the month solution
2. allows creative flexibility
3. intuitive, won't require weeks to learn and months to master  
Should I start diving into Django and learning how its MVC works?  Everything I've read pisses on Django, but seems like the most used option for GAE.  
I'm sorry if this isn't coherent. These technologies are out of my comfort zone, so I have trouble searching for solutions and phrasing my questions.