Make the picture smaller before sending it. You're limited to 600k at most (some carriers may still be on the old standard of 300k).
Unless you're sending it to someone on an iPhone - that's something that's cropped up recently, and there's no fix for it on the Android end yet.