A class 4 from a good manufacturer, like SanDisk, will be adequate. Anything faster would ensure best performance.
The capacity/cost issue is usually dependent on what you want to use the phone for.
(A class 4, 8GB SanDisk SD card came as standard with the phone in UK.)