Did we first have swimming birds or flying birds?
Flying came first, as far as we know. The earliest known bird (currently), Archaeopteryx lithographica, already had aerodynamic feathers (Feduccia and Tordoff, 1979). The Solnhofen Limestone, where it was discovered, is ~145 million years old, so we can place the "when" flight evolved to greater than or equal to that time.

Gansus yumenensis is regarded as the earliest aquatic bird and is dated from ~120 million years ago. The Hesperornithiformes are the sister taxon of Gansus (less derived) and also aquatic. However, they date from ~85 million years ago. It is not clear whether the ancestors of Hesperornithiformes were also aquatic. Because they branched off the main line of birds before Gansus, these ancestors would likely predate Gansus, but those relatives have not yet been discovered.