This is correct behavior.
Google discontinued EAS support for free (Gmail) accounts around January 2013 (July for Windows Phone 8). If your device did not already have EAS configured before that cutoff date, then google will refuse to set up EAS. It sounds like your Windows Phone was already set up, but your desktop was not:
Google Sync End of Life
Google Sync was designed to allow access to Gmail, Google Calendar, and Contacts via the Microsoft® Exchange ActiveSync® protocol. With the recent launch of CardDAV, Google now offers similar access via IMAP, CalDAV, and CardDAV, making it possible to build a seamless sync experience using open protocols. Starting January 30, 2013, consumers won't be able to set up new devices using Google Sync, however, existing Google Sync connections will continue to function. Google Sync will continue to be fully supported for Google Apps for Business, Government and Education users who are unaffected by this announcement.
If you want to set up a new device with EAS, you must be linking it to a Google Apps for Business/Education account.
Currently, Windows 8 provides IMAP support in the Mail application, but there is no way to do 2-way syncing of calendars or contacts because neither CalDAV and CardDAV are supported by the Calendar or People applications.
Google Apps for Business is $5/month/user, so I ended up just setting up that for myself on my personal domain with me as the only user and migrating to it.
On top of this, I think Microsoft added a block in Windows 8.1 that prevents adding m.google.com as an EAS server, which sounds like the error message you are running into. I'm still trying to find a way around this.