I've finished MegaSokoban - port of my early game (for AVR TV game - http://uzebox.org/forums/viewtopic.php?f=10&t=914
) for Uzebox.
It's not audio or video excellent, but it's right choice for Sokoban maniacs, because it has 999 levels (all of them fitted into 664's FLASH thanks to use of my compression algorithm developed for original purpose - yes, loading levels from SD card is better solution to store more levels, but I didn't want to change engine a lot).
Levels are selected from collections Microban, Sasquatch by David W. Skinner and Procedural Sokoban Level Generation - algorithmically generated by Joshua Taylor and Ian Parberry. I've not solved them all yet, but they're guaranteed to be solvable by their authors (but compression bugs may screw it a little, so I don't guarantee, that every can be solved).
What's special for this game is it's video mode - I call it mode 10, it's generally mode 5 with changed tile size to 12x16 pixels, and there are 16x12 tiles on screen (total resolution 192x192 with black border around). I was to lazy to make instruction counting for time-perfect scanline length, so I used oscilloscope & TV to make it work by trial-error method. I hope it will work on your TV. What's good on this mode is, that it doesn't occupy much RAM (around 3KB free), and tiles are so big, that mapping between vram and game world are 1 to 1 (vram is actually used to store game data and character printing functions to load level).
I think it can be useable for games with simple graphics (not many tiles and no sprites or scrolling) and complex memory-intensive logic. There wasn't need for so much RAM in sokoban, but I wanted to play with videomode. Then I've used free RAM to make 1000 pushes undo buffer (you can go 1000 pushes back in time).
More info on wiki: http://uzebox.org/wiki/index.php?title=MegaSokoban
UZE file attached, I'll commit source to trunk, if Uze don't mind, that I'll make little changes to kernel (add new video mode).