We detect angular galaxy-QSO cross-correlations between the APM Galaxy Catalogue and a preliminary release (consisting of roughly half of the anticipated final catalogue) of the Hamburg-ESO Catalogue of Bright QSOs as a function of source QSO redshift using multiple cross-correlation estimators. Each of the estimators yield very similar results, implying that the APM catalogue and the Hamburg-ESO survey are both fair samples of the respective true galaxy and QSO populations. Though the signal matches the expectations of gravitational lensing qualitatively, the strength of the measured cross-correlation signal is significantly greater than the CDM models of lensing by large scale structure would suggest. This same disagreement between models and observation has been found in several earlier studies. We estimate our confidence in the correlation detections versus redshift by generating 1000 random realizations of the Hamburg-ESO QSO survey: We detect physical associations between galaxies and low-redshift QSOs at 99% confidence and detect lensing associations at roughly 95% confidence for QSOs with redshifts between 0.6 and 1. Control cross-correlations between Galactic stars and QSOs show no signal. Finally, the overdensities (underdensities) of galaxies near QSO positions relative to those lying roughly 135 - 150 arcmin away are uncorrelated with differences in Galactic extinction between the two regions, implying that Galactic dust is not significantly affecting the QSO sample.