A pac man clone would be pretty good too, though you’d need to implement some kind of AI. There are several threads about the A* method of path finding that could help with this.
As to the changes in BGE… Lots of changes, but not a lot of changes… Capabilities have been somewhat improved and there are other changes already commited to Blender 2.5. View frustrum culling has been implemented/improved and the scene graph has gone through some changes to optimize it, but this is all behind the scenes so you will only notice a performance increase, no change in how you’d make a game.
Occlusion culling has been introduced to help optimise complex scenes. Access to bone positions has been added to the action actuator so you can get/set poses using Python in realtime. It is now possible to reinstance the physics mesh (after changing the mesh on an object or after deformation, but it is quite a heavy function so is best used sparingly). ideasman42 has recently been sponsored by the community to include dynamic loading/freeing of content (think like streaming content live from the net). This is not currently threaded and there are no plans to add threading to it, but this may be added in the future.
The Python API has been revamped somewhat in preparation for 2.5 and implementation of Python 3.0, but this is mainly syntax changes that make things much simpler. Much of the API also runs faster than it previously did. if you’ve not done too much BGE Python before then you need to be aware that some older tutorials are outdated, but support for the old API is still there so you can still use the old methods. If you know the old API well, you’ll notice that some things have changed in the API documentation, but the old methods still work for now.
This is a basic overview of the changes and there are many others such as memory leak fixes, etc. There are probably also new features that I’ve missed or forgotten. Everything works as before but better, but there are also a load of new goodies that have been added and more that are slated for the future.
Have fun with the new, improved, improving BGE.