FPGAs or CPLDs for "Glue Logic" and Video/LCD Capabilities
FPGA's are more expensive than CPLD's, but they can do so much more too.  I only use CPLD's where the "instant on" (i.e., no programming time) is required, or when I need something that costs less than US$5 per chip.  For everything else, an FPGA is preferable over a CPLD-- in my opinion.
Rarely does it make sense to put a CPU INSIDE the FPGA.  When it comes to bang for the buck, you just can't compete with an off the shelf ARM or something similar.  The only times it makes sense is when you only need a tiny 8-bit micro (a.la. Xilinx Picoblaze), or you are using an FPGA that includes a hard core and space is more important than cost.  For your application, you'll need a reasonable 32-bit CPU to render the graphics for the LCD.  So, at the very least, you'll have a 2-chip solution (CPU + FPGA/CPLD).
Yes, FPGA's need to be programmed at power-up.  This can be a good or bad thing.  It's bad because it means that at the very least you need a small Flash EEPROM chip that they "boot" from.  It is good because it means that you can easily do "in the field firmware upgrades".  With a CPLD, you'd have to drag out the CPLD programmer hardware/software every time you need to do an upgrade.


For most of the boards I've designed, I've always had a CPU that took care of programming the FPGA.  That CPU has been Power-PC's, ARM's, and an Intel Atom.  Since that CPU already had Flash, RAM, Ethernet, and Linux it was a piece of cake to implement the FPGA drivers and FPGA programming stuff.  

In your case, I would lean toward CPLD's rather than FPGA's.  Here's why:


Implementing a video output circuitry in an FPGA is not trivial.  If I were assigning that task to an engineer, I would not assign it to a Junior engineer.  It would have to be a Sr. engineer with 10+ years of experience.  A Jr engineer might be able to "make it work", but it wouldn't be very good.  Since you need a 32-bit CPU anyway, you might as well get one with a video output-- like some T.I. ARM's have, as well as the Freescale iMX stuff.
For those big shift registers, you need very little logic and a lot of I/O pins.  More specifically, you need about 4 Flip-Flops per I/O pin.  A medium sized FPGA will have maybe 300 I/O pins, but 50,000+ Flip-Flops.  So you are really paying money for things you will never use.  In the end, I think that you will spend about double or triple for an FPGA solution than a CPLD solution.
For someone who is just starting out with programmable logic, CPLD's have a much easier learning curve.  There is no sense in making things more complicated before you have to.


And here is another bit of unsolicited advise:  Stick with the big FPGA/CPLD people (Xilinx and Altera).  Avoid the 2nd and 3rd tier manufacturers like Lattice, Actel, Quicklogic, etc.  The big guys are no more expensive (or not significantly so), their tools and support are better (and free!), and the skills you learn will be easier to use on future projects.  And most importantly, it will look better on a resume!