You'll find character LCDs with parallel inputs most commonly in 16×2 and 20×4 configurations, but other widths and heights are possible. There's not much mystery behind whether they work with ATmega328P-based Arduinos: they are the go-to solution for most display requirements. Their biggest issue is their appearance. This is partially mitigated by there being displays of various quality available. But that doesn't change the basic aesthetics. If you can't tolerate the looks, you'll have to opt for a graphics display.

Arduino has a LiquidCrystal library that supports Character LCDs. In addition, there's Greg Tan's BigCrystal library, which builds on top of the LiquidCrystal library and adds support for clever double height characters. As sort of an acid test, I decided to get an idea of what the processing time and memory overhead for using BigCrystal was.