The audio effect of harmonizing with parallel 5ths can be a lot more palatable to most ears if you use a combination of 4ths and 5ths. You get the same medieval-ish sound, but you choose either the 4th or the 5th so that you don't go out of the key of the melody. This requires you to come up with a harmony and learn it rather than just singing or playing the melody a 5th up.