Charizard: +Dragon
Gyarados: +Dragon
Lapras: maybe +Dragon (or Rock like most dino Pokémon)
Dragonair: +Water and Flying (maybe Water for Dragonite, too)
Noctowl (and maybe Hoothoot): +Psychic
Ledian: +Fighting since it has boxing gloves and can learn several punching moves
Gligar line: +Poison since they're part scorpion
Delibird: I could honestly see +Fairy with its Santa theme
Lugia: +Water (maybe even Dragon, or swapping Psychic for Dragon)
Mega Swampert: +Fighting
Masquerain: +Water
Sableye: +Rock
Mawile: +Dark
Aron line: +Ground (I sometimes mistake them for Steel/Ground)
Hoenn fossils: +Water
Staraptor: +Fighting
Lucario (and maybe Riolu): +Psychic, because aura
Gallade: +Fairy for its elvish appearance
Stunfisk: +Water
Dragalge: +Water
Incineroar: +Fighting
Golisopod +Fighting (and/or Steel since it looks like it's wearing a suit of armor)
Solgaleo: +Fire
Cinderace: +Fighting, because kicking
Inteleon: +Dark
Mr. Rime: +Fairy
I also agree with adding Fairy to Celebi (and most other mythicals), Bug to the Trapinch line, and Flying to all Pokémon capable of flight.
Avatar by cheerymori