You may need to use a combination of sensors. I can't think of any single sensor that can reliably detect the different surfaces.
An IR sensor could detect the difference between grass (cooler) and pavement/gravel (warmer).
An ultrasonic ranging sensor could detect the difference in heights between the grass and pavement/gravel.
A photoelectric sensor could detect the difference in reflectivity between the grass and gravel/pavement.
A visual camera could be used with image processing to detect color differences, although this may be too processing intensive for an Arduino.
A final possibility would be measuring the resistance to movement of the wheels. The robot will travel easier over the hard surface of pavement/gravel.
I would think that a combination of the above sensors would provide the most reliability and accuracy. However, it will still likely be limited to one location without recalibration. The weather will even cause a change in some of the sensors (photoelectric for example on a sunny vs. cloudy day).