Watching DS9 and heard the phrase 'it is a good day to die' and couldn't remember hearing it in early TNG episodes, but thinking it surely it came from TNG first, I just can't recall which episode and who said it.
Canon and book answers are viable, but looking for real world timing, not in-universe (ie - if it was first written in a book and then incorporated into the series later, that is fine (and interesting) but a book written in 2015 about the history of Khaless uttering the phrase centuries in the past wouldn't count)