All Electronics http://www.allelectronics.com has some LCDs on sale which seem pretty close to ideal for a Mega169 project. There is no datasheet, but a user has reverse-engineered and found them to be 4-1/2 digits top row, 3 digits lower row, with a few text blocks.
The Mega169 can't handle all of the segments at once, since this display is 31x2 and the M169 is optimized for 25x4. Stock number is LCD-99 and price is four for $1 USD.
I have not received mine yet so I don't know any more than this (such as voltage compatibility, etc.)