Or is stepping within the bounds of the city enough? Assuming I walk into a city for the first time and immediately try to use fly, would it fly me directly to the Pokemon Center despite me never having been there, thus saving me the effort of having to search?
Thanks in advance, Rex
Generally, simply entering a flyable location is all that is required to be able to use Fly for that location. There are some exceptions, however, such as Opelucid City in Black and White where the player must first view the Team Plasma event, Lacunosa Town in Black 2 and White 2 where the player must first encounter Professor Juniper and Bianca, and Ever Grande City in Ruby, Sapphire, and Emerald where the player must first climb the waterfall. The Johto Battle Frontier, by contrast, can automatically be accessed after the National Pokédex is obtained.
No, most of the time, you do not have to have visited a Pokemon Center in an area that you can fly to in order to fly to it.
Source