This is an old revision of the document!
Character LCDs with parallel inputs are available all over the place. The most common formats are 16×2 and 20×4, but you can find other widths and heights as well. They're available with either positive or negative rendering and in a variety of backlight colors. They cover a range of quality, with serviceable STN displays running just a few dollars.
There's not much mystery behind whether they work with ATmega328P-based Arduinos: they do. They are the go-to solution for most display requirements. Their biggest issue is their appearance. This can be partially mitigated by using an FSTN or higher quality units. But this doesn't change the basic aesthetics. If you can't tolerate the looks, you'll have to opt for a graphic display.
A second issue is that they consume a lot of pins. There are I2C adapters available for the parallel interface though, which you'll be able to read out in this wiki sooner or later.
Arduino has a LiquidCrystal library that supports character LCDs using the Hitachi HD44780 parallel controller and equivalents. In addition, there's Greg Tan's BigCrystal library, which builds on top of the LiquidCrystal library and cleverly adds support for double-height characters.
I decided to get an idea of what the processing time and memory overhead using BigCrystal with a 20×4 display was. I used a 5V 16 Mhz Nano, and the display is probably an STN unit. The reported frame update time is around 14 msec and varies with the number of big characters being drawn. Memory use is 15% of program storage and 6% of dynamic memory. Because these numbers are so low, I didn't bother doing a test of the LiquidCrystal library on its own.