The $footer_links string has line breaks hard coded in, and now that you're prepending some text to each link the lines are longer and look odd when they wrap. You might want to try this and see if you prefer the look:
$footer_links = $categ->makeFooterLinks();
$footer_links = str_replace('">', '">My Text ', $footer_links);
$footer_links = str_replace('<br />', ' | ', $footer_links);
I would avoid using the <center> tag, as it's a depreciated tag, and it's better to use CSS to center text. It's also better not to wrap the footer links in a <h3> tag, as it's not a heading and I'm guessing you're doing it for styling purposes, in which case again it's better to use CSS.
and in your css file:
color: rgb(77, 80, 89);
/* add the lines below */
padding: 0px 50px;
font-family: "Trebuchet MS",verdana,arial,sans-serif;
You'll probably want to play around with the padding to get it looking the way you want.