The stretch Vigo - Tui, is not my strong point. I have driven the stretch Vigo - Portugal border several times. I would guess Vigo Airport to Tui is about a 30-40 minute drive if you choose a taxi (maybe 40-50 euros, my guess).
We'd like to start as early as possible. So since I don't want to gobble up time going into Vigo & out again (we'll already have a long flight from the northwest US, to Madrid, and then to Vigo) - I'll probably hire a taxi and look at the 40 to 50 euros as part of the travel costs. My wife has some limited physical ability, so we need extra time (compared to most). The Portuguese route seems the best since there are fewer strenuous sections (mountains, required long days). We'll be probably launch the third week of September (in 2006, not 2007 like I said before).
the mountains in Galicia are in the east on the Castillean border, so if you start to the west of them - say, Sarria or Ourense - none of the routes is particularly strenuous. However, the Portuguese route is the most populated, so there are more towns and hence accommodation. I found it scenically the most attractive of the routes in Galicia I've walked.