I see no reason why you can't make that with the iPhone API right now (with 3GS hardware). It might be faster with a native OpenGL ES implementation too.
Well, the very first thing that I wanted to implement was something like this:
http://code.google.com/p/android-scripting/
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.