Yeah, I gave them a shot but the texture still gets messed up :/
I did a weird workaround by using "gui box" with no background/style, and set the box image to the texture I need - this helps the image not look AS compressed and weird (I guess Unity handles guibox differently than draw texture), but it's still not perfect. Additionally, using Gui Box gives less control over the size of the image - changing the box size doesn't change the image size, it's strange.
I wonder if there even is a way to optimize image shrinking within Unity's GUI, or if I'll just have to create a separate set of GUI images for each possible resolution X_X