Given that Earth has a much stronger gravitational pull than the Moon, how does the Moon have any influence on Earth's oceans?
Everything in the universe has a gravitational influence on everything else in the universe. It isn't a question of the strongest gravitational pull winning out and all the others doing nothing.
The Earth is the strongest pull on the oceans, but the Moon and the Sun both have easily measurable effect in addition to the Earth's. Other bodies (Venus, Jupiter, a small asteroid in another galaxy,....) all have much smaller effects which will be hard or impossible to detect amidst the noise due to waves and so on.
The following diagram from the wikipedia article on the tidal force shows the tidal force that results from a moon.
Note that the tidal force is directed away from the center of the planet when the moon (satellite) is directly overhead or underfoot but is directed toward the center of the planet when the moon is on the horizon. You are right that these very small influences. The tiny changes in the vertical component of the tidal force from the Moon on the Earth have very little effect on the oceans.
What does matter are those places where the angle between the line segment from the center of the planet to the moon and the line segment from the center of the planet to a point on the surface is approximately 45° or 135°. The tidal force is purely horizontal in those places. Minuscule as that tidal forcing is, this horizontal component of the tidal forcing function is unopposed by gravitation the Earth itself. This horizontal forcing makes the waters "want" to flow sideways.
The direction of this flow changes constantly due to the Earth's rotation. The Coriolis effect comes into play precisely because the Earth is rotating. The shapes of the oceanic basins and continental margins also come into play. The end result is a set of amphidromic systems, each of which involves large scale oceanic waves that rotate about amphidromic points.