Si sólo vas a cambiar la estructura de tablas a div's, hazlo sin dudarlo. Ten en cuenta que si no cambias el contenido, va a ser el mismo al fin y al cabo antes y después, sólo cambia la estructura, por lo que no te va a afectar (negativamente) al posicionamiento, en cualquier caso lo único que te podría pasar es que o te quedaras como estás, o notaras una mejoría (por lo de cambiar a div).
Los links internos no es un problema, al contrario, es beneficioso para ti, denota que es un sitio grande, con variedad, y si el contenido también es tuyo original, ya es fantástico.
Pd: Tengo pendiente abrir un post para hablar de un experimento que hice hablando de la importancia de una estructura u otra de cara al SEO. A ver cuándo tengo un hueco y lo posteo.