My instinct is that "every other day" is vastly more common than "every second day" - and NGrams confirms this. Both are correct, though.
(It is interesting to note that the use of "other" to mean "second" goes right back to Old English, whereas the word "second" is much more recent, not attested until 1297. Still, there are many contexts in modern English in which only "second" is permissible. You can come first or second in a race, for example, but you can't come "other".)
"Every three days" and "every third day" are both acceptable too, and here the difference in frequency is much smaller, but recently "every three days" has had the edge, according to NGrams.