To get to the point, we recommend using ImageMagick or GraphicsMagick if available and allowed to use the exec() function in PHP. You can change that in Gallery 3 by logging in as an administrator, then going to Admin > Settings > Graphics.
A bit more background; Gallery 3 ships with the ability to use one of three different graphics toolkits, GD, ImageMagick, or GraphicsMagick. By default GD is the enabled toolkit because we can make a pretty good bet that it's available in nearly every standard PHP install.
However, GD is not the most efficient toolkit to use for most people. GD is part of PHP and shares any memory alloted to PHP, so for most who have memory limits set in PHP, GD eats into that really quickly.