Non devi installare solamente il provider ADO.NET di FireBird, ma anche il client di FireBird.

Questo comunque non è un problema legato a VB.NET, ma si parla di deploy di FireBird.