I'd say you should probably err on the smaller side. You can get a higher angle stem or a longer fork or a fork extender or some handlebars which arch back upwards to make the smaller bike fit you.

if you go large, you may have the same issues that you already have.

Are there multiple bike shops around you? The one you're currently at doesn't seem very good at actually doing bike fit.