I guess I was lucky as there were lots of people also in the area who were all talking about it then headed off so I was able to follow them. Yellow Gremllin have the Outrider marked on the map in the South Shroud and Thanalan:

YG map

This is also where I saw him, so it sounds as if that's where he normally appears.

Also, the Imperials seemed to be spawning between where the outrider is and the new settlement Buscarron's Fold. They ran south from there to the outrider unless people engaged them en route.