Both are absolutely stellar games and, truth be told, I consider them a single game.
Galaxy 1 was a Mario game for everybody, new to the series and old timers like myself. It wasn't mind-numbingly hard, but it wasn't too easy. It was an incredible game and I loved every minute of it - I just wished it were a little bit harder. Along, then, comes Galaxy 2. In contrast, Galaxy 2 feels like a game for us, the old timers. It was brutally difficult at times and was just as wonderful as the original game.
Thus the edge goes slightly to Galaxy 2, even though they're both perfect games.