What I'm doing is making a bit CPU. It's a nice rounded out way to cover all the basics.
You'll cover all the basics of a large project in VHDL and be exposed to all of the core topics in VHDL design (clocks, inputs, outputs, logic, buses, and sequential design most prominently) as well as many core electronic and computer design and architecture concepts like registers, data operations, memory, and computer arithmetic.
You can start with just addition and subtraction and then add more functionality as you learn, working your way up to a fully functional (albeit simple...or as I prefer to call it "retro") computer. At least, that's my plan.
Plus, having your own custom-designed computer on a chip is just plain cool :) Like a 16 bit Raspberry Pi :P
Other common FPGA projects:
-Music synthesizer
-DSP effect generator
-MIDI controller/interrupter
-Bitcoin miner
-Video game console emulators
-Custom Arduino shields
-Parallel processors (very useful for certain mathematical problems that conventional computers aren't great at)
-Robotics/control systems
-Data acquisition (fair few oscilloscope designs out there for FPGAs if you know how to work with op amps)
VHDL on its own isn't horribly complicated. The most important thing to remember is that you're designing a physical electronic digital circuit, not writing a program for a microcontroller. Your simulation is not a program that is going to run line by line, basically, so don't let the superficial similarity to C fool you, VHDL is a very different paradigm.