Asumiendo que estás usando la agenda de Google y que los contactos no están siendo almacenados en la tarjeta SIM, todo lo que necesitas hacer es configurar tu nuevo dispositivo con la misma cuenta de Google que usaste para configurar el o los teléfonos anteriores. Si estás almacenando los contactos en la SIM, hay una opción en los contactos para moverlos a los contactos de Google.
En cuanto a la instalación de tus aplicaciones, cualquier aplicación que hayas pagado se descargará y reinstalará automáticamente desde el Android Market (de nuevo, siempre que utilices la misma cuenta de Google en ambos dispositivos). También puedes utilizar servicios como AppBrain para crear listas que luego puedes utilizar para instalar masivamente aplicaciones en otro dispositivo.
Yo recomendaría el uso de Copia de seguridad en titanio para hacer una copia de seguridad de las aplicaciones en un dispositivo a su tarjeta SD, a continuación, transferir la tarjeta SD a los archivos de copia de seguridad al nuevo dispositivo, instalar Titanium Backup en el nuevo dispositivo, y luego restaurar desde allí. De este modo, también conservas la configuración de las aplicaciones. Sin embargo, no hagas una copia de seguridad de la configuración del sistema, ya que pasar de un modelo de dispositivo a otro puede ser problemático.