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 are the go-to solution for many display requirements. Their biggest issue is their appearance. This can be partially mitigated by using an FSTN or higher quality unit. 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 may be able to read about in this wiki if I eventually work with one.
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 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 4% of dynamic memory. Because these numbers are so low, I didn't bother doing a test of the LiquidCrystal library on its own.