I'm using Atmel's AT45DCB004 4MB DataFlash card, which actually uses an AT45DB321B internally. Although it is page based (528bytes/page) it has 2 RAM page buffers so you can be writing to one buffer while the other is being written to flash. You can interface directly with the AVR via SPI, it uses a standard 7 pin MMC connector and I've developed a very simple (1 regulator, 2 caps & 3 res) parallel port PC interface for downloading data.
As an example of storage capacity my application is storing a record every minute comprising a 7byte timestamp, 2x16bit integers and 5bytes of status, and I can fit 187 days worth of data into 4MB.