In order to facilitate the management of network connectivity between the client networks and the provider network, in some embodiments a connectivity coordinator responsible for implementing one or more programmatic interfaces through which connectivity-related requests from clients are handled may be set up. A variety of different kinds of connectivity-related requests, such as requests to discover the types of connectivity options that may be accessible, requests to select a particular connectivity option or service, requests to set up or dismantle a physical link, and the like may be made available through the interface in different implementations. The interface may be exposed to the client in many different ways in various embodiments: for example, as an API, through a graphical user interface, a web page or web site, or even as a collection of commands that can be issued from a computer system's command-line prompt.