1) Recomendar un host es algo complicado. Prueba en
www.buscahost.com y cuando tengas dos o tres nombres investiga por la web (incluyendo forosdelweb) la reputación del host
2) Tendrás que tener mas claro lo que quieres. "Correo gratis de gran capacidad" no significa nada. Una cuenta de 25 megas pop3 es mas que suficiente para el 99.999999% de la gente. Y una de 1 mg es suficiente para el 80+%. Si el acceso es webmail el tamaño ha de ser mayor.
3) Los archivos se subiran de varias maneras. Por ejemplo el cpanel tiene un papel para subir archivos, podrías usar este. No obstante lo normal es que te ofrezcan acceso via FTP y uses este protocolo para subir las páginas. Hay programas de pago muy baratos y buenos para subirlo y algunos programas freeware de gran calidad.
4) Los trámites no serán mucho mas complejos que elegir host, rellenar un formulario de datos y pagar con tarjeta de credito u otro medio alternativo (paypal, epagado, transferencia bancaria, ...)