Doesn't matter what I do, I can't seem to push the arm all the way, even though the bolt is tight and it feels stable:
I just replaced a worn out and damaged arm but they look similar enough to not have this gap (old on the left, right is new):
Crank arm looks like it is actually fully on the tapered part of the axle. Square taper cranks don't mate up to the frame bottom bracket shell, there's supposed to be a gap there.
See: Sheldon Brown's page on square taper cranks/bottom brackets.
The gap does look a bit large to me though. Are you replacing crank arms? (Crank arm in pic looks new.) Is there a difference in fit of new vs old arms?
Update after pic of old crank added.
Wow! You really did let that crank get bad! Old crank arm that badly damaged would sit further onto the axle because the taper has been enlarged.
I'd take the bike to your local bike store and ask them to tighten the crank bolts up to the proper torque with a suitably large torque wrench (they'd likely do this for free or for a nominally small charge) to avoid recurrence of the issue.
Update 2: for reference here’s an old BB and crank I dug out. Bolt is not torqued down, but it shows where crank sits on the taper.