GUI-embeddable Python drawing widget with anti-aliasing
If you don't mind the way GTK looks, pygtk has an option for antialising in their canvas widget (see this) and is considered by many to be as powerful as Tkinter, though it is not included in standard Python installs.
Also, it's Python 3.x compatible, which can't be said of most non-standard library modules and packages.
Screwing around with Tkinter+pygame is silly. I would use wxPython. In fact, I've done a diagramming widget using wxPython, and it has anti-aliasing:
Unfortunately it was for work, so I can't distribute the code.
The wxPython classes you want to look at for anti-aliasing are wx.GCDC and/or wx.GraphicsContext.
After a thorough search I ended up using PyQt4. It does fit all my requirements (Python 3, cross-platform, anti-aliasing), and now that I've gotten through the basics, it's also quite intuitive and easy to use.
Posting this as an answer to my own question and accepting it for future reference.