Nethack

Nethack is definitely doable, but there isn't a Java port so it would have to be a compiled binary exposed through a Java GUI.

I'm not sure if Kindlets are allowed to call random binary programs or use JNI; I suspect not. This is obviously not a problem for rooted devices as you can just change what they're allowed to do.

However, KIF as it is would be runnable on a non-rooted device, except for the signatures.