I guarantee the things you are thinking of are implemented in microcontrollers, not FPGA's. FPGA's aren't even that good at state machine type logic - they excel in parallel tasks which make the most use of each (longer) clock cycle.
Similar to the NAND to Tetris article posted earlier, when I went through college, we built a microcontroller using Altera EPROMS. I had been programming for years prior, and understanding how the ALU could be performing many simultaneous calculations only switching the output based on the opcode, completely changed my perspective.
The newer FPGAs sound pretty nice and significantly more capable than what I've worked with. Definitely something I'll keep in mind.
