> implementing a program with the same API should be fine, right?

If this is all it comes down to, Google certainly should be fine with it being that they're in the middle of (end of?) a lawsuit with Oracle over their implementation of the Java API in Android.

Middle of still. Oracle filed for appeal of their most recent loss[0].

[0] http://arstechnica.com/tech-policy/2016/10/its-official-orac...

Amazon has been providing drop-in replacement implementations of Google APIs (for proprietary Google services) for some time now. For instance:

"The Amazon Maps API offers interface parity with version 2 of the Google Maps API. Most classes and method calls in your Google Maps app work the same on Amazon devices. "

https://developer.amazon.com/public/apis/experience/maps/doc...

I would imagine the problems they might have with this project is that it, I assume, calls private remote Google APIs -- which would by definition be an unlicensed use.

Nearly the entire point of the project is to have an Android system that isn't reliant on Google services.

Edit: I see I misunderstood. This page talks about opting in to Google services: https://github.com/microg/android_packages_apps_GmsCore/wiki

So they are using them.

What does breaking a terms of service mean legally though? Like they're spoofing the signatures so it all appears to google that it's the same, so I'm not sure how they'd enforce it?

They could use their safetynet to check