When I had my 1999 VX, I changed the stock Bridgestones out and added Yokohama Geolandars all around. These were VERY good all-purpose tires, and not very spendy.

They get excellent reviews, too.