My first time through any Zelda game, I pretty much always give Link the same name. I used to just call him Link but for a long time now I call him Axle, just because other people in the house I live in play the games and it helps keep our files separate.
Any time I decide to play through again, or do a 3-Heart Challenge or Minimalist Run, though, I have fun with the names.
I've only done this with PH and ST so far, but in PH I named him Kraken, and in ST I named him Cobalt. I picked Kraken because it's a squid-like sea monster, and Cobalt because it has a sound to it that feels like it belongs in Spirit Tracks, so they're not exactly random, but they are still odd.