Forget Nano. Mega has 8 MB on memory and it is nearly minimum, where you run NMEA library and some other code. You can run it on Uno, if you disable several things from library.
I prefer to go to Teensy 3.2. It is small and fast and has 64 MB RAM. If you like, you can compile it to 24 MHz and run it with 13 mA from 12V. I had that as temperature monitor reading several DS1820 sensors and sending data to NMEA2000. And still would have plenty of flash and RAM for other things. Other good choice would be ESP32, but it has worse ADC and requires lot of corrections to reach 0.05 V accuracy over 30V.
For both Teensy and ESP32 you need only tranceiver (e.g. MCP2562) and DC-DC converter.
And about power I have to remind to avoid ground loops in your system. If that is risk, would be better to use isolated DC-DC and ISO1050 tranceiver.