Eric, Can you recomned what I should look for in a flash chip if I go down that road?
That depends.
1) Are you going to write to it a lot, if so look at Atmel, they have some chips with internal write control.
2) What is the timing of the uC you use.
3) be prepared to go 3.3V, the flash offerings in 5V are not expanding.
4) for reasons I have forgotten, I look first at ST micro when looking for flash, currently I'm using a 2Mbyte that cost ~$2.505)
5)I do not use external code flash, with internal code flash, I get ISP and the associated PC software for free.

Erik