It was fun playing the old Infocom games on Frotz (just add the Z3/Z4/Z5 sources using the file transfer feature on iOS). For iOS, the sources are at http://code.google.com/p/iphonefrotz/ and http://sourceforge.net/projects/jfrotz/ is an Android port for those who prefer to roll their own.

How does Frotz deal with the "no interpreters" rule in App Store?

Technically, the rule is "no interpreters that download code". To get around it, it bundles a decent chunk of the if-archive in the app and then registers as something that can open z-machine game files (so you can use Frotz to open a game from Dropbox, after downloading in Mobile Safari, etc.).

I like Frotz as well - play it on my Windows Phone 8 (Nokia Lumia 928)