First of all, thanks for playing!
You are on the right track! Once you reach the Hydro Plant, Bilbi and Isu appear there. Bilbi is the guy with the shotgun. The character who mentions the Earth Spire in the base is actually a different character and the king can be found elsewhere.