Hey, Tom! I've seen your AI-1 remote and it's very impressive. I thought about following your plans, but it seemed a little more complex than I want/need. In retrospect, I'm not sure my code is that much simpler, relatively speaking. I am fairly happy with my menu system, however. You can see my code in my public SVN repository.
I'm planning on going the same route as you with the Atmega chip: I'm just going to make it all part of my circuit. It looks like core functionality can be retained with just a crystal, provided you're doing your own power conversion. I want to go with AA or AAA batteries because I've already got a bunch of NiMH cells, and my charger won't work with a 9v battery. Hopefully the Maxim chip mentioned above will do the trick.
This (eBay listing) is the display I got for $5 plus shipping. If the Hantronix display I saw on Jameco is the same as yours, they're the same size, but it adds a backlight (and is half the cost ;)). I'm planning on putting a timer onto the backlight so I'm not drawing juice from it all the time. I've also added contrast control to my menu; not sure how often that'll have to be tweaked...