It's not a theme issue.
When you insert an image into a post, WP creates a version of the image in specific dimensions. The HTML of the image on your latest post, for example, is this:
<img src="http://fc01.deviantart.net/fs70/f/2010/153/a/d/suddenly_a_pier_by_awjay.jpg" alt="" width="720" height="349" />
When you change theme, the code remains the same (unless you edit it), so the dimensions of the version displayed remain the same (except in some themes that constrain the image to the available width no matter if the code asks for a wider one). You can make the images adapt to the width of each theme by removing the height command from the code and changing the width command to this:
width="100%"
Of course this will only work well if the originals are wider than the available width of the theme, otherwise they'll be blown up and become pixellated.
PS You understand that the phrase "the pics you copy/paste from other sites" is a very questionable phrase.