Kira/Odo is hardly last-minute. True, "His Way" takes place in mid-late Season 6, but the possibility has been discussed since Season 3's "Heart of Stone". In addition, "Crossfire" (Season 4), "Children of Time" (Season 5), and the "Call to Arms"-"Sacrifice of Angels" story arc (Season 5-6) all make Odo/Kira a major plot point.