So, here is where we are:
I have changed the graphics loading mechanism to use "atlases," large images separated into tile blocks, instead of the many individual images used before. This will make improving the graphics a lot less annoying. The tile size has also been increased to 32x32, which fits less onscreen at once but gives a better view of the world. We'll see if it's a good change with play testing, it won't be hard now to change it back.
The two most promising leads for performance improvements are Cython, a Python-to-C converter, and OpenGL. In the first case, that is something best saved for much later. In the second, the PyOpenGL library has a bug that prevents its installation under Python 2.6, so that's going to have to wait for now.
Today is mostly devoted to graphics work. I'm considering character designs for the main guy. I might temporarily import Aurora from Mayflight to fill the role, but she's 16x16 anyway. She'd make a good placeholder though.