I always keep "Link" the same. It's a matter of nostalgia and love. I LOVED that LoZ:TP let you change the horse's name. I named that ***** "Agro" (Shadow of the Colossus, anyone?) sodamnfast. I hate "Epona".
In Pokemon, I name them after mythological figures. And in RPGs... my first run, keep the defaults. The second run, I extrapolate what I know about the characters and name them appropriately.
There is a single exception. In Rune Harvest, I was so appalled at the boredom inherent in the name "Raguna" and named him "Astraeus," Greek god of astronomy and father of the four wind gods- One of which is "Zephyrus", where I get my catch-all multiplayer name. If you ever see a "LadyZephyrus" on a free MMORPG, it may very well be me.