So, I'm trying to set up a rather strict grid system and wondering what the "rules" for dealing with the gutter and the baseline. Should they have the same value?
By baseline, I'm assuming you mean leading or the baseline grid? ...Because the baseline on its own is just where the type sits, there's no measure that I can think of for a single baseline.
If you take into account the gestalt principles of proximity, you would want the gutter to look larger than the leading so that people's eye flow to the next line in the text instead of hopping to the other column. And for the same reasons, you would want your margins to be wider than the gutter.
There are a few rules of thumb, that i know of:
gutter width ≈ line spacing
gutter width ≈ width of »mii«
Too much is a little bit less problematic than too little spacing between columns.
These rules should be seen only as a starting point to a proper solution.