Are there any good apps for android for navidrome/jellyfin respectively?

Symfonium is paid but by far the best i tried. Will work with both via subsonic api.

how easy can I add songs to them/do they pull metadata from somewhere (like jellyfin does for movies)

I use navidrome and can't speak to jellyfin. Navidrome is intentionally read-only for security reasons so you add music to where navidrome can see it and it'll auto-scan them in. For metadata my recommendation is musicbrainz picard. A lot of people recommend beets and it can be good but it's a big learning curve. Musicbrainz picard has a nice gui and easier to get music matched for beginners.

how do they (or any other options) compare in terms of ease of setup/maintainability?

From what i see people use jellyfin because they don't want "yet another container" and most people already have jellyfin for other media content. So that would be easiest route. Navidrome isn't hard to set up though, and overall has a better feel for me.

do you have any overall recommendations?

Look into LRCGET to get the timesynced and/or plaintext lyrics of your songs. There's also a navidrome plugin that will automatically fetch the lyrics when a song is played

Edit: for desktop id recommend feishin. It'll work with both through subsonic api