Per eliminare il fatto che al rollover il link si sottolinea basta che aggiungi nel tag <a questo codice:
<a href="percorso" style="text-decoration: none">

Per quel che riguarda il cambio di colore devi utilizzare dei fogli di stile css settando all'hover un colore diverso.