Gallery shortcode output is handled by gallery_shortcode function.
If you look at the source code I linked you can udersand there are different way to customize the output:
Using filters
You can completely override gallery output using 'post_gallery' filter.
Customize size via atts
One of the argument you can pass to function using shortcode is 'size', it can be used to make shortcode use a specific image site, one of the default or one custom registered via add_image_size.
E.g.
Will make gallery use non resized image.
Customize using CSS
You can disable the addition of default gallery style by returning false to "use_default_gallery_style" filter hook.
You can also change / edit it using "gallery_style" filter hook.
Consider you can use the .gallery-item, .gallery-icon.portrait and .gallery-icon.landscape classes in your CSS.
Using plugins
In the official WordPress plugin repository there are 1385 gallery-related plugins, and if you look in GitHub and in different markteplaces there are hundreds of other.