Sin que se instalen los runtimes en la máquina no se puede porque VB no permite crear ejecutables stand alone. Tienes que utilizar el asistente para distribución para crear el instalador.
Crealo entrando a Inicio/Programas/Microsoft Visual Studio 6.0/Herramientas de Microsoft Visual Studio/Asistente para Empaquetado y Distribucion.
Y como su nombre lo indica te guiara en la creacion de tu instalador.
Suerte