Regularity and Variationality of Solutions to Hamilton-Jacobi Equations. Part I: regularity