From experience with most providers, Heroku has been the fastest and easiest to deploy to. It's interesting to hear an alternative experience. What would you say got in the way for you?
A lot of the problem is that I develop in Aptana / Eclipse, and the file layout that Aptana expects is different from what Heroku expects (Aptanas has one extra directory at the top level, yet Heroku expects some of its files in the top level directory).
In the end I have a slightly hacky try / except around some imports in urls.py to get around the problem.
That's what I mean by learning curve.