|Another solution I have read was use vector graphics, wouldn't this make collision essentially exponentially harder?|
Your graphics engine should have absolutely nothing to do with your collision detection. So no... your collision detection should be the same regardless of sprite graphics, vector graphics, or no graphics.
That said there are a number of ways to approach this problem:
1) Vector graphics -- make a 2.5D game instead of a 2D game.
2) Pick an aspect ratio, then scale up/down the image to match that ratio. For example say your "natural" output image is 640x480 and the user is using a 1920x1080 res... you could display your image as 1440 x 1080 and have "black bars" on the sides.
3) Combine technique #2 with a "mipmapping" technique. Basically where you have different images for "low res" displays and "high res" displays. For example, you could have one copy of the player graphics where each frame is 64x64, and then scale that image down manually and have a copy of it which is 32x32. Then in-game, use whichever size requires the least stretching.
4) Use technique #2, but only allow integer scaling to prevent 'blurring' and maintain a 'pixel-sharp' image. So instead of outputting 1440x1080 as mentioned in #2 (2.25x ratio) you would output 1280x960 (2x ratio). Then have "black bars" on all 4 sides.
There are other approaches as well, but these are just the ones I came up with. Each have their pros and cons, so it's up to you to decide which one you prefer.