Are there any free and open-source navigation apps for Android, under 50MB?

What you're asking for is fairly unrealistic. The only way this could work sustainably would be for something to exist where you host your own tile server and routing service and patch that into OSM. Otherwise, even if the app itself is open source, the backend will cost money to run and will be proprietary.

The reason that OSM is able to be fully open source is because you host the tiles on your phone and do the routing calculations locally.

OSMand~ has an online mode...
I can't think of any reason the backend can't be open-source too.
- It costs money to host something like that. You want low latency, real-time routing and tile-rendering? Even more money. Sure, it could be funded by donations or something like that, but I'm not holding my breath.
- You're right. There is (are?) an open source web interface to OSM. Technically, someone could host that themselves, and the app is just the web browser.
  The real reason that it's not common is because there's no demand; or, at least, not enough for anyone to take the effort to package it up in an easy-to-deploy, well documented release. And demand is low because having offline, local tiles is almost always preferrable to nav or maps that require relatively heavy, constant internet access.

No

The current FOSS offerings do the calculations on your device, so you'd need the maps downloaded locally. The small apps that stream their tiles from OSM/Jawg/ESRI/Mapbox etc. don't support navigation because of this

Not FOSS but the closest thing you'll get to this is GMaps WV on F-Droid, made by the DivestOS team. Even that does not support navigation though, it only provides directions (usable for me, your mileage may vary...)

Not under 50MB but there is: https://organicmaps.app/

And

https://osmand.net/

I find Organic Maps best for driving and OSMAnd+ best for walks.

Organic maps can't even handle addresses. How is this useful for driving?
- Yes it can. You need to download the necessary maps first before you can search for addresses though.
- It does handle addresses.
- Street address data isn't available for the US. I find the POI in Google Maps in Firefox and then go to Share and open the coordinates in Organic Maps or OsmAnd.
- It handles addresses well

I like organic maps cause it does shit locally, offline. It has to download the maps though which is certain to be larger than 50mb. What you are looking for is a cloud based maps solution like google maps and you aren't going to find that in foss space

I don't know the size, but Organic Maps may be rather small

Then there are these two:
https://android.izzysoft.de/repo/apk/io.github.janbar.osmin
https://f-droid.org/packages/com.junjunguo.pocketmaps/
But I have no experience with them

Under 50mb is a very hard ask. Maps have a lot of data.

Not foss but magic earth is a great app that does not rely on google maps. It can also work as a dashcam.

Gmaps WV on F-Droid?

Looking for the same thing for Linux fwiw, with live turn by turn navigation and GPS support.