Am I wrong, or is the Democratic party just larger than the Republican party and therefore more mainstream?

I'm not sure that's supported by the evidence. Gallup polls show Republican party as smaller than the Democratic party (23% v 28% in 2013), but that difference is made almost entirely of 'leaners'. Other polls that track solely identification rather than lean don't show this disparity, and the Gallup numbers have little predictive power over primary turnout trends.

It seems to me that people like Rand Paul and Ted Cruz would have to get called flip-flops if they were to run for presidency in 2016 while Hillary Clinton would be able to run just one campaign.

Is it that Hillary Clinton is less likely to be considered a 'flip-flop' than Ted Cruz, or that voters likely to vote for Hillary Clinton are less likely to care if someone calls her a 'flip-flop'? Conservatives are not likely to wait before pointing out her positions on the gas tax, on gay marriage, on several health care related matters, on several foreign policy matters, et all. Progressives are unlikely to do so, but progressives also have historically found it useful to portray Republican Presidential candidates as far-right stalwarts as possible. The specific complaints and criticisms are going to reflect the values of the folk professing them, and different political affiliations often have different values.

To some extent, weathervaning is just a natural result of any system that includes primary elections. You've got more tools to excuse it when it's your side, but that's doesn't mean it doesn't happen.