You should look here. It will give you some idea on what's available in Iceland. As to where to purchase the SIM you'll probably have better luck in the main shopping areas but if it's like it is in Europe you may be able to get a SIM kit at small shops as well. As for your "ouch" that's the way it is with prepaid pretty much everywhere. The only way to get a better data rate is to be a billed subscriber and that's probably not likely unless you have an Iceland credit file.