Our plan for this year includes quadrature optical encoders, a gyro, absolute magnetic encoders, rangefinders (either IR or Ultrasonic, but of the vareity that returns an analog value and not that you have to send a high to ping and you have to use an interrupt to receive), and possible an accelerometer. This is going to be a blast
I have some code written for all of them if you want to see.
As for starting location not working on anything like that, I haven't run into any such problems yet. Are there any specific scenarios you have in mind?