I'd say they were able to, and that they did; SNES beat the Megadrive 49 million to 29.5 million, so by over 60% more consoles sold. (http://www.vgchartz.com/analysis/platform_totals/)

And Nintendo didn't have "all the advantages" either; Megadrive had a headstart which they fully capitalized on by advertising how much more capable their system was over the ageing NES. The Megadrive was certainly not a weak opponent; Sega were at the top of their game in the late 80s and early 90s, don't let their dismal performance later on fool you as to how formidable they were in their prime.

I don't think sega was a pushover. But that they were ahead of SNES until they lost focus. Which just shows that Sony coming more structured than Sega they would likely oversell N64. Still SNES was stronger, more well know, with more partners, and momentum from NES. They had much more advantages than they would against PS1.

Megadrive were ahead at first because they had a headstart, same as 360 was ahead of PS3 for most of the 7th gen cos it launched a year earlier.

I don't see how Sony would have any more of an advantage over a CD-based N64 than Sega had over the SNES; in both cases it'd be a matter of the challenger getting a head start and having good advertising, but Nintendo getting the combination of the biggest third and first party big guns and more capable hardware.

Gotta pay closer attention. In the alternate scenario that I brought up about Sony not entering the market, I never mentioned the N64 being CD based.

I'm going off the assumption that in that alternate reality, the Nintendo 64 still goes with cartridges, while the Sega Saturn is the only one using discs. And because the Nintendo 64 wouldn't launch until June 1996 in Japan, September 1996, and March 1997 in Europe, that would give Sega an extra year to prepare for the Nintendo 64 and a near 2 year headstart in Japan. And because there would be no PlayStation, there's no pressure on Sega of America coming from Sega of Japan to go with the ultimately bone-headed move of rushing the Saturn's launch to beat the PlayStation to the market, because they've got an extra year. Which means they can take their time, prepare a proper marketing campaign, give retailers enough time to prepare their stock, and build the strongest launch lineup possible for a late 1995 or early 1996 Western release. More importantly, because the Saturn would have been the only CD-based system in this alternate scenario, that means Square (Final Fantasy VII, VIII, and IX), Enix (Dragon Quest VII), Konami (Metal Gear Solid), Namco (Tekken), Capcom (Resident Evil) and all the major Japanese 3rd party franchises that jumped to the PlayStation would have jumped to the Saturn instead. It would've required more work to program for the Saturn's architecture, but it would've been much more preferred than the archaic, restrictive, and costly choice of sticking with cartridges on the Nintendo 64. That means the Saturn would have thoroughly dominated in Japan. (It was already the best selling 5th generation system and outselling the PlayStation until Square dropped the Final Fantasy VII bomb, and from that point on, it was all over for Sega and Nintendo in Japan.) That would not only have drastically changed Sega's fortunes in Japan, but everywhere else as well. Especially since the Western 3rd party support that the PlayStation enjoyed so much from franchises like Tomb Raider, Grand Theft Auto, Crash, Spyro, etc. would've gone to the Saturn, with no other CD option available. Even if Nintendo were lucky enough to get N64 versions of those games, they would have been noticeably worse than the Saturn versions because of the difference in format. Because of all this, I’m convinced the Saturn would’ve been victorious in a no PlayStation reality where they were the only CD system vs a cartridge-based Nintendo 64.

As for your second point:
1) They DID significantly outsell the Genesis. It ended up winning the U.S., barely lost in Europe, and completely dominated Japan. 
Final Worldwide totals:
SNES - 49.10 million
Genesis - 29.54 million.
A win by almost 20 million units. That's pretty significant to me, especially given how much smaller the market was back then. 
2) Because all the exclusive 3rd party games and franchises that pushed the PlayStation to the heights it achieved, in Europe and everywhere else, would have either been multiplatform or Nintendo 64 exclusive. So the biggest advantage that the PlayStation had going for it? It's massive, more diverse, mostly exclusive game library? *snaps* Gone. Nintendo would've been the one with the bigger and wider library. And games sell hardware, don't they?

So the two systems that have very similar 3rd party libraries, with the Nintendo 64 having the slight edge in that department, with the absolute final nail in the coffin being Nintendo's 1st party offerings. Sony's 1st party offerings were piss-poor back then. Gran Turismo, Hot Shots Golf, and PaRappa the Rapper would not have cut it against the likes of Super Mario 64, Ocarina of Time, GoldenEye 007, Banjo-Kazooie, Super Smash Bros., etc. Those games would have been significantly different with a CD format instead of a cartidges, but Nintendo, being the acclaimed and proven game developers that they were and still are, would have found a way to make those games just as groundbreaking, acclaimed, and iconic in that alternate reality as they were in this reality.

It's simple common sense:
If both systems have Tomb Raider, Final Fantasy, Tekken, Metal Gear Solid, and all these amazing 3rd party games. They both cost the same price, what's the deciding factor at that point? First party. Do I go with the system that has cars, golf, and a rapping dog? Or the one with Mario, Zelda, and all these other familiar franchises everyone has known about since the 80s? A Nintendo 64-CD's supercharged library that still has all of Nintendo's 1st party games + all the 3rd party games that the PlayStation had, some of which might still be Nintendo exclusive like Final Fantasy VII, which blew up and was the biggest killer app the PlayStation had? I shouldn't have to explain how much this would have radically flipped the tables of the 5th generation.

Europe and RotW would have gradually gone to them in much higher numbers, because Nintendo would have had a lot more reasons for them to do so and they would have given them more reasons to do so once they saw the rapidly expanding market. It would'v'e been pretty fucking hard to say no to a system that had Super Mario 64, Ocarina of Time, Final Fantasy VII-IX, Metal Gear Solid, Tekken, Resident Evil 2... Almost every single major 3rd party 5th generation game (minus Crash and Spyro) that drove the PlayStation to the heights it reached + the major, groundbreaking 1st party 5th generation games that carried the Nintendo 64 all in one system? If you honestly can't see how a system like THAT would have achieved massive numbers, in all territories, within a rapidly growing industry at the time, I have no idea what else to tell you.

Nobody is saying that all these companies would continue making exclusive games for Nintendo.

What we are saying is that the games that were exclusive to PS1 and made the system likely would also be on N64 had Nintendo not gone the cartridge route. Even with sour relationships, they kept making SNES games (usually the superior port that sold better) so it's reasonable to say they would continue the next generation had Nintendo provided them a media that they could easily fit all the sound and audio these companies needed when entering the new 3d gaming world.

Even if Nintendo didn't dominate in America, it would likely have kept its lead and it would have dominated in Japan. Europe wasn't as big a market as it is now so even if PS1 won that area, I still firmly believe N64 would have been the worldwide market leader.

Various thoughts.

• The N64 would NOT have cost $200 at launch. Though I'm having trouble getting precise information, CD-ROM disc drives were still fairly expensive in the mid-90's. I found an old article from 1996 talking about how they cost "less than $200."
• Third party support in general would still have favored the PlayStation. Even if we look at games released on less successful platforms like the 3DO and Saturn, it's clear that companies were looking for a new platform to support that wasn't from Nintendo. I think that the main support Nintendo would gain would come from Squaresoft and Enix, who dropped their N64 plans fairly late. This would have most of its impact within Japan, which would support the N64 the most this generation.
• Although losing its core JRPG's would mean the PlayStation would lose in Japan, that would not be enough to kill it. According to Famitsu, PlayStation and Saturn software sales were roughly on par in 1995 before the PS1 took the lead in 1996, well before Final Fantasy VII was released. Even without Square or Enix, the PS1 had plenty of games sell very well in Japan alone, even early in the platform's life. In Japan, PlayStation would get by for two years on games like Ridge Racer, Tekken 1/2, Resident Evil, and Arc the Lad, before getting some of its biggest titles in 1997 (Gran Turismo, Resident Evil 2, Hot Shots Golf, Tales of Destiny, etc).
• In the West, the PlayStation would be hurt even less. Even in real life, Final Fantasy is mostly remembered as a small component of an overall strong lineup for the PS1. Gran Turismo, Tekken, Crash Bandicoot, Spyro, Metal Gear Solid, Driver, Tomb Raider, etc.
• What I find most interesting is how Nintendo's own games would be effected. How would Ocarina of Time be hurt by long load times? How would improved textures and storage help it? Would a lot of classic Nintendo games include badly aged FMV's? Could games like Super Mario 64 have featured more level?

Precisely. CD-Rom drives were more expensive, stamping a CD though was cheap as chips.

Carts slots on the other-hand only cost peanuts to implement, but building cartridges was expensive as hell.

I am not able to find any accurate info other than CD-R drives being $1,000 at around 1995.

I admit I did not factor disc drive cost into the OP. Still, the PS1 was $300 USD at launch back in 1995, so surely CD drives can't have been that expensive.

Like I said in my first post, the cost of the system would be a factor, but the fact that the games would be so much cheaper would largely negate that. N64 games were ridiculous in how expensive they were.

It seems to me that Nintendo could have gotten away with using cartridges instead of CDs if they hadn't screwed over Sony with the SNES disk drive. If there was no Playstation third parties would just have to figure out how to work with the N64. The Saturn would likely have been even less viable as a 3d system than it was in real life, since they hastily changed the hardware to be 3d capable in response to the Playstation. Developers would just have to figure out what Factor 5 did with its audio compression and Capcom did with Resident Evil 2. It would be more difficult, take more time and money, but there would be no other option for them. Nintendo made two huge blunders in the 90s, screwing Sony over and going with cartridges. They could have gotten away with making one of those blunders as long as they didn't do the other, but by doing both they effectively killed their home console line.

Nintendo has always had this weird issue with worrying so much about losing out on relatively small sources of income that they end up losing millions for the sake of a few bucks. The deal they made with Sony was a bad deal, but the disk drive was never going to be a big hit anyway if all the Sega add-ons of the era are anything to go by, so they would not lose much by just sticking it out. Piracy was a problem, but by worrying so much about it they handicapped their system and sold tens of millions of units less, a far greater loss than piracy could ever cause them. They repeated that mistake to a lesser extent with the Gamecube, using those mini-disks in order to combat piracy and losing out on more third party support because of it. And in recent years they've had that stupid Youtube policy where they've been penny-pinching youtubers not realizing that they were strangling free advertising for their products. Talk about not being able to see the forest for the trees.

Yeah. I see lots of posts saying CD drives were expensive and yes, there were some expensive CD based consoles (CD-i and 3DO come to mind from Phillips and Panasonic--two other companies that specialized in electronics and tried to break into the gaming industry like Sony). but when the N64 dropped, the PS1 and Saturn immediately dropped their prices. N64 may not have been $199 but I think it would have been close.

And to be honest, the $199 price was a shock back then even for the N64. Everyone expected $250 and then $199 came out of nowhere!