I assume that 신혼 여행 밤 is more like "honeymoon night", but I'm wondering if there is any difference between 결혼 첫날 밤 and 신혼 첫날밤?
Also, are there any other terms for "Wedding night" that I've missed?
결혼 means marriage and 신혼 means newly-wed. In this view, 신혼 여행 is the term used for honeymoon. We don't use 결혼 여행 for honeymoon.
For wedding night, 결혼 and 신혼 is redundant. Most people say just 첫날밤.
When rhyme is important, or in poem, some people use 초야 (Chinese word) in place of 첫날밤.
In addition to Chul-Woong's answer, the word 첫날밤 has a very obvious connotation of "We're having SEX tonight!": it is in fact often used to just mean "first sex" (between a new couple), or for humorous effects, e.g., "오늘 새로 산 Xbox와 첫날밤이네요."
Anyway, I think "결혼 첫날밤" or "신혼 첫날밤" would both sound the same. If you want to sound more neutral, you could probably say "결혼식날 밤" (literally "the night of the wedding day").
Also it might not coincide with "신혼 여행 밤" ("honeymoon travel night") because many couples start their 신혼 여행 the day after wedding. (Korean wedding is an extremely demanding and tiresome business.)