There are much less extreme options to try before doing what's suggested above. The key is to fit the shadow frustum as close as possible to the view frustum and shadow casters onto that frustum. Get your Z depth as tight as you can, boost the shadow precision if you can, make the shadow area smaller if you can. Try centering the shadow in front of the camera. Explore Z precision tricks like reversed depth planes.
That said, I haven't tested screen-space soft shadows yet but this might be an intrinsic part of blurring in what is basically the wrong domain.
Depends entirely on what you're doing.
Is it a point light or directional? Either way there's multi sampling the shadow map is going to improve it, but is going to take up much the same performance hit as just increasing shadow maps size. There's also temporal anti aliasing. The idea being you slightly shift the projection of the shadow map each frame, keeping the last frames results to combine with the new ones. It's basically multi sampling over time, but has issues with moving objects.
If it's just a directional shadow, say from the sun, then things get a bit easier. Cascaded shadow maps use multiple shadow maps projected towards the sun, in a neat kind of shadow LOD trick. http://developer.download.nvidia.com/SDK/10.5/opengl/src/cascaded_shadow_maps/doc/cascaded_shadow_maps.pdf There's also a much more advanced version of this this that I have bookmarked somewhere, and I can't remember the name of. Regardless it advances on cascaded shadow maps to the point where you can get results that are basically alias free.
Anyway, hope that helps.
PS Holy shit this text editor we've got nowadays is a piece of trash