Symphony of the Night was the first XBLA game the go over the 64MB limit on Xbox 360 - at about 90MB. It had the FMV ripped out, and yeah, an N64 version would have been easily doable with music compression but it probably would have to be more like remixed music due to the different sound hardware and the technology at the time not being good enough to compress audio to a degree to fit in on one cartridge. It's worth noting that the first 64MB cart games were in 1999 so by this point a lot of the games mentioned were already done with for the most part.
Thinking of this...is there even a single side scrolling game on N64 with the classic pixel art style? I know there was Bangaio, that has a very unique look.
The thing about N64 that really stinks is that, without modding the system, there is a filter applied to everything - two of them, in fact. Developers could disable part of this chain but you still ended up with blurry output compared to competing systems. Would be curious to see what it would look like.
On top of that, N64 would have run into the same issue as Saturn with SotN specifically. The game runs at 256x224 as a result of pulling some assets from the PC Engine Rondo of Blood title but I don't think N64 supports this resolution (Saturn doesn't either).
So they would have to scale everything or pillar-box. The art was scaled on Saturn and looks awful - on N64 it would likely be blurred.
From what I understand, doing traditional 2D pixel art on N64 isn't exactly a trivial thing either. On PS1 and Saturn, 2D is generally rendered to a pair of triangles without lighting or transformation so it eats up a lot more memory than tile and sprite based systems. Saturn had a second VDP that could specifically handle tile based backgrounds, though, which helped.
N64, though? I wonder if the memory limitations would have made it difficult to achieve high-quality 2D pixel art.