Hmm, have a look at the videos at YouTube about line followers with and without PID control of the robot.

Behaviour of non PID is similar to your nervous car. The same robot with PID control slides smooth on the line (or in your case follow the wall in a steady distance).

Why not give it a try?

Here is the same robot with and without.

http://members.jcom.home.ne.jp/felm/ltc_p.mpg
http://members.jcom.home.ne.jp/felm/ltc_pd.mpg

Ioannis