You can look around at the "PC-104" format systems I guess, and maybe non-standard format boards; which one you choose depends on what you need. Just note - none of these are 'cheap'.
Some manufacturers which come to mind include:
DSP Design (www.dspdesign.com
The first two are highly recommended, I haven't dealt with 'DSP Design' but I've been looking at their products, and I've found Advantech too frustrating to work with (maybe just crappy technical support here in Australia).
You might also want to have a look at the 'GumStix' computer, although I have no idea if it supports an LCD display.
As for those LCD displays - the multiline Alphanumeric displays come in models which use a serial port to set up the display - if that's the sort of LCD you have in mind. If you're thinking of the type used in PDAs, then you need a board which explicitly supports LCD displays - have a look at the "supported displays" if the manufacturer has such a list, then look at reviews of those particular displays.
Since you probably need buttons as well, you want support for a "keypad". You may need to write your own driver to scan the keypad, but sometimes the manufacturer provides a reference driver for Linux.