Most of the microcontrollers have a very limited amount of storage. The Uno, for instance, has 32K of flash, and couple KB of RAM. That's quite a bit of code space, but not much for image data. You can use one of the big guns chips like the 2560 to get 256KB of flash, but even that isn't exactly a ton of space for bitmaps.
JPG and the like are out of the question, in terms of needing horsepower and memory enough to decode the compressed data, so you trade format efficiency for storage space.
SD has oodles of space, so that solves your problem. And it's super easy to hook up, physically. The library is large (code space again), so at least a 328P (Uno) for sure, considering the needs of the LCD library as well. But since you no longer have to care about having enough room to store pictures on-flash, that's fine. The rest of your sketch looks like it'll need minimal space.
The one downside (maybe -- depending on your viewpoint) of the Adafruit screen is that it's also touchscreen. If that doesn't fit in to you UI needs, it's a waste... Changing screens means you'll need to ensure your new LCD has a chipset with a pre-built library capable of handling the image reading and displaying. (Or code your own.) But, if you decide that using a touchscreen might work with your project, then you're all set.