The JS API makes extensive use of JSONP, and this is how service metadata is retrieved. Once the JS API knows about a map service, it can insert tags to display map tiles or images from dynamic map services.
You're correct that there are certain cases where a proxy is required. You can read up about them in the "Using a Proxy" section of the Inside esri.request help topic.
Edit: Providing more info below about how esri.Map, map services and geoprocessing services work.
Accessing map services from the ArcGIS Server REST API does not require a proxy or CORS. This is because map service info can be retrieved via JSONP, which circumvents browsers' same origin policy. Once a map service is created and added to a map, the map tiles (or map images if the service is not cached) are inserted into the page by creating img tags. You can see this if you look at a page's DOM via Firefox or Chrome's developer tools. Since img tags (as well as script and link tags) are not subject to same origin, this works without a proxy or CORS.
For GP services, things are a little different. GP services usually take a number of inputs, and the request (the URL specifying input parameters) to a GP service is usually quite long. Because certain browsers impose a limit on URL length, to ensure cross browser compatibility, the JS API will switch to doing a POST rather than a GET when a URL is longer than ~2k characters. Cross domain POSTs are prohibited by same origin, and this is why a proxy (or CORS) is required. If you are using a GP service that accepts a small number of inputs, and only accepts a point (lines and polygons quickly increase URL length because every vertex is specified part of the request), it is possible possible to use GP service without a proxy or CORS. The key thing to remember is that if a URL is less than ~2k characters, and the request can be completed with a GET request, a proxy/CORS are not required. If the request must be done via a POST (an edit operation, for instance), and the service you're using is not on the same domain as your application, a proxy or CORS is required.