Hi. I just found this thread and can confirm that, without a ESRI account (free or paid) I'm not getting a basemap selection. It's no problem for me in that I just sign in with my account. I was helping a friend through the same problem and, even with a new account, he's not getting Basemaps. Likely to do with being behind a firewall. Another solution is to go to the ArcGIS Server:
In ArcGIS Explorer, go to Add Content ==> Choose GIS Services ==> Server Type stays as ArcGIS Server ==> in the server box, paste in http://services.arcgisonline.com/arcgis/services; don't worry about username or password ==> Next. Choose your map from the list then Add Service.
That choice will now always appear when you Choose GIS Services. Just Highlight it under Select a Service and click Next. Also, you get more map choices with a direct connection to their map server.