the concept of eternity is far more mind-boggling than how the universe started to me for some reason. It makes me physically ill thinking about the possibility of my soul floating around for "eternity".
Yeah, but the eternity part is the part about the universe starting that I can't grasp. "it's always been there" isn't a valid answer for me. And, if it hasn't always been there then I need to know where it came from and "it came from nothing and a huge explosion made it something" is not a valid answer for me either. 
Either something always was or something came from nothing.
Don't both of those violate laws and stuff?
I'm also unconvinced by the "infinite regression" explanations. It just strikes me as the scientific equivalent of "turtles all the way down", like replacing "god" with "time" to explain whatever we don't understand.
Yep. I mean, it almost has to be that our laws of physics are not valid anywhere else. Like we are just some podunk county that has our own laws of physics that don't apply at any of the infinate (< though this really won't apply anywhere else) other places out there that have completely different laws. So, time is like just another dimension and doesn't exist while some other dimension does that we can't comprehend because it doesn't exist in our existance. Plus, we could never know of it's existance because their physics and laws or whatever don't mesh with ours. I think I'm sounding like a crazy bum on a street corner rambling here but whatevs.
A step in the right direction is to realize that time IS just another dimension. When dealing in relativistic dynamics, you use a 4-vector (ct,-x,-y,-z) instead of the regular 3-vector (x,y,z). The whole idea is that space and time are not separate things, but one unified concept: space-time.
Both space and time manifested themselves at the moment of the Big Bang. The Big Bang wasn't an explosion into anything, but a rapid expansion of everything. In fact the Universe is still expanding. For the most part every galaxy in the Universe is rapidly accelerating from every other galaxy in the Universe.
As for the edge of the Universe, well when cosmologists talk about the size of the Universe they mean the size of the
observable Universe, how far away can light reach us. The Universe at this point in time (IMHO) is expanding so rapidly that for all intents and purposes there is no edge, the "edge" is always moving away faster than the speed of light.