Hmmm... good question.
How are we counting this exactly, though?
I think on some level mine would be Tetris for the Game Boy, released in 1989. Except I bought that in about... 1996/7 or so, so it would be a slightly later release I suppose. Does that count as 1989?
If it does, it would be Tetris. Otherwise... probably Destruction Derby on PS1 from 1995 that I personally own. We got out first PC in 1995 too, and my brother still has Command & Conquer from slightly earlier in the year.
EDIT: Oh, I just remembered... I have a cassette of Hercules: Slayer of the Damned for C64! Apparently, that's from 1988 though... so I only get better by a single year.