This was before we knew that the iPhone wasn't planned to ship with a native API (or that the eventual API and the phone itself would be so crippled), but for a brief, shining moment, I saw a world where everyone had a real computer in their pockets, always connected.
I really ought to go through my notes and implement some of those exuberant ideas for Android.
(To my delight, at least one of them has already been made: Google Sky Map. It's also smarter, as it uses GPS to determine where you are; my idea was to use the camera and image processing to recognize constellations).
Well, the very first thing that I wanted to implement was something like this:
1. Interpreter/VM with arbitrary code.
2. Open Source
Until recently, VOIP was banned, as well.
Aside from decent notifications and real background tasks (and the aforementioned Locale, which was also on the list), the biggest blockers are the App Store and its restrictive policies.
Free at Last, brother! :)