HTML5 sin duda. A pesar de que hay navegadores que aún no entienden las nuevas tags de HTML5 (como IE8), como bien has dicho, este lenguaje te permitirá estructurar mejor tu web semánticamente, con la adición de nuevos elementos como nav, aside, article, etc.
Como recomendación, si vas a utilizar HTML5 es conveniente que utilices un archivo de normalización para tu CSS (
http://necolas.github.io/normalize.css/) y otro de reset para que los browser que no reconozcan las nuevas tags no hagan estragos en tu diseño.
El tipo de DOCTYPE es indiferente de cara al SEO, aunque debe siempre estar presente en el encabezado de tu web.