The spark happens because a current WAS flowing and then is interrupted and arcs through the air to try to keep flowing. With a clean set of contacts this almost never happens when you START a circuit by plugging in a device that is turned on already, because before the plug-in there is no existing current flow. It is VERY common, however, if you UNplug something that's on. The effect is more prominent for heavy current user devices, or for ones with medium-to-large motors (because of inductance - but that's getting too complicated).
Since your situation is when you PLUG IN I'd suspect slightly dirty contacts involved. You say you already have replaced the outlet, so I would assume its metal surfaces are clean and its springy contacts are tight. That leaves us with the prongs of the plug you are pushing in. Examine them for discoloration and maybe clean them a bit by scraping or with a abrasive like emery cloth. With dirty contacts on the plug blades, as you push it in there can be momentary contact to establish a current flow, followed by a momentary disconnection at a dirty spot that interrupts the current flow and causes the arcing.