What hardware to use?

Building an odometer, there's one overriding requirement: measure how fast the car is moving and/or how far it has moved.  For my use, I'm going to take a fairly universal approach: build a wheel sensor that signals rotations - most modern cars have a speed sender signal that can be tapped, but that's much more invasive than a simple wheel sensor. 

Odometer Goals

In case you missed the backstory, here's the short version:
I'm building a high-precision odometer (aka "rally computer") as my first Arduino project.

So, aside from refreshing my embedded skills, and learning a fair amount about the Arduino environment, what should this project do?

The Department of Backstory

Some days, writing code is fun.  Other days, not so much.  For me, the realization that all the code I had written in more than three years did nothing more than change pixels on a screen or twiddle bits on a hard drive meant it was time to start something new.