I've tried giving lutefisk to the lutefisk statue quite a few times now and I've noticed I seem to get some items pretty consistently (macuahuitl & cracked orbs are pretty common) but it seems like it's all mostly lower tier items. Does the floor level affect the quality of item?
Floor level, as well as number of lutefisk you give, I believe. In general, you won't get a useful item. I have gotten plenty that were usable, just not relevant to my character. I've gotten a small number of items that I have actually used, though.
It seems that the lutefisk shrine would be one situation in which it would be reasonable to give the player an item that they're more likely to be able to use. After all, the entire premise of the lutefisk shrine is that you're turning all that junk you don't want into lutefisk, hoping to get something you actually do want. By "appropriate" I mean e.g. weapons appropriate to weaponskill, robes for characters with more mage levels than anything else, crossbows for characters with the archery skill, etc. Of course, even if the item type is appropriate there's no guarantee that it'll be better than what you already have.
I believe the item is guaranteed 1 enchantment for every 100 lutefisk (up to 500) and yes the quality depends on the floor you donate.
It seems to me that it's a lot easier now to get an item with fewer than 100 lutefisk (generally a really poor item). I suggest that you don't donate anything until you have at least 100, but preferably a lot more than that.