He podido medio solucionar el tema, lo publico por si a alguien le puede servir:

Básicamente lo que he hecho ha sigo hacer coincidir la resolución de N64 con la resolución nativa del televisor. Me ha servido este tutorial: https://github.com/recalbox/recalbox-os/wiki/N64-:-return-to-ES-(EN)

Con los comandos "tvservice -m DMT" y "tvservice -m CEA" he sabido qué resoluciones soporta mi TV:

Group DMT has 11 modes:
mode 4: 640x480 @ 60Hz 4:3, clock:25MHz progressive
mode 5: 640x480 @ 72Hz 4:3, clock:31MHz progressive
mode 6: 640x480 @ 75Hz 4:3, clock:31MHz progressive
mode 9: 800x600 @ 60Hz 4:3, clock:40MHz progressive
mode 10: 800x600 @ 72Hz 4:3, clock:50MHz progressive
mode 11: 800x600 @ 75Hz 4:3, clock:49MHz progressive
mode 16: 1024x768 @ 60Hz 4:3, clock:65MHz progressive
mode 17: 1024x768 @ 70Hz 4:3, clock:75MHz progressive
mode 18: 1024x768 @ 75Hz 4:3, clock:78MHz progressive
(prefer) mode 81: 1366x768 @ 60Hz 16:9, clock:85MHz progressive
mode 85: 1280x720 @ 60Hz 16:9, clock:74MHz progressive

Group CEA has 16 modes:
mode 1: 640x480 @ 60Hz 4:3, clock:25MHz progressive
mode 2: 720x480 @ 60Hz 4:3, clock:27MHz progressive
mode 3: 720x480 @ 60Hz 16:9, clock:27MHz progressive
(native) mode 4: 1280x720 @ 60Hz 16:9, clock:74MHz progressive
mode 5: 1920x1080 @ 60Hz 16:9, clock:74MHz interlaced
mode 7: 720x480 @ 60Hz 16:9, clock:27MHz x2 interlaced
mode 16: 1920x1080 @ 60Hz 16:9, clock:148MHz progressive
mode 17: 720x576 @ 50Hz 4:3, clock:27MHz progressive
mode 18: 720x576 @ 50Hz 16:9, clock:27MHz progressive
mode 19: 1280x720 @ 50Hz 16:9, clock:74MHz progressive
mode 20: 1920x1080 @ 50Hz 16:9, clock:74MHz interlaced
mode 22: 720x576 @ 50Hz 16:9, clock:27MHz x2 interlaced
mode 31: 1920x1080 @ 50Hz 16:9, clock:148MHz progressive
mode 32: 1920x1080 @ 24Hz 16:9, clock:74MHz progressive
mode 33: 1920x1080 @ 25Hz 16:9, clock:74MHz progressive
mode 34: 1920x1080 @ 30Hz 16:9, clock:74MHz progressive

En mi caso he escrito CEA 4 HDMI (eligiendo para estos emus la resolución nativa de mi TV 1280x720) en recalbox.conf y noto mucha más suavidad en los gráficos y más fluidez en los juegos que con la resolución que venía de serie (800x600).

La emulación sigue sin ser perfecta pero... esto ya lo sabíamos! XD

Aún así, sigo teniendo algún tironcillo en Mario64 que con la versión anterior de Recalbox no tenía. Ahora por lo menos ya se puede jugar. Si alguien conoce más arreglos para estos temas, que lo diga! 🙂

Ah, y por cierto, esto también sirve para Dreamcast!!