I just published my second game for the Google Android. In Maze Escape, you can navigate through a random 2D maze between 5x5 and 100x100 squares. Maze generation is a little slower with larger mazes, but not much.
I tried to put a lot more into the game than you'll initially see. I plan to add some of those features in the next release: more options, animations, and elements of gameplay.
Here's a screenshot of Maze Escape: