Your ARC app is badly outdated. If your Core is on earlyaccess, your ARC app (and all remotes) must be as well. The current version in earlyaccess is ARC 1.0.10 Build 100139.
Android Auto was first introduced in Build 116 but was only available as an APK:
And through the Play Store with Build 129:
If you installed ARC from the APK package, you can get the current one here:
Or consider uninstalling it and installing ARC (and earlyaccess Remote apps) from the Google Play Store, in which case you should get automatic updates (if you didn’t turn them off). Ensure that the Play Store recognizes that you should get Beta updates.
Alternatively, if you don’t want to use earlyaccess and return to production builds:
Your ARC app is still out of date. The one that brought Auto to regular production releases is 1.0.10 Build 138:
In this case, ensure that your Core runs production, as well as ARC and all remotes. To leave earlyaccess, see here.