After cross-comparing the Wikipedia List of Spacewalks (split into several pages) and the List of International Space Station expeditions, I have discovered the following:
Timothy Kopra, on Expedition 46, arrived at the ISS on December 15, 2015 at 17:33:29 (all times UTC). He then conducted a spacewalk at December 21, 2015 at 13:45. That's 5 days, 6 hours, and 27 minutes after arrival.
Andrew Feustel and Richard Arnold (Expedition 55) arrived at the ISS on March 23, 2018 at 20:40. Their spacewalk was conducted on March 29, 2018, at 13:33 (Fairly certain I did the time conversions correctly). That puts them at 5 days, 16 hours, and 53 minutes after arrival.
That means that Timothy Kopra holds the record for soonest spacewalk after arrival, by 10 hours and 26 minutes.
Expedition 22 and Expedition 35 both had spacewalks where cosmonauts went out just under a month after arrival, but those were the next soonest. Other than that, it was at least a month between arrival and going on a spacewalk.
As Organic Marble pointed out, James Voss and Susan Helms conducted a spacewalk on 11 March 2001 at 05:12 UTC, after docking on 10 March 2001, 06:38 UTC. That puts their spacewalk less than 24 hours after arriving at the ISS. However, this spacewalk was nominally part of STS-102 rather than Expedition 2, and the astronauts conducted the spacewalk from the Space Shuttle rather than the ISS. So within the framework of the question ("spacewalks staged from the ISS"), it technically doesn't count. Just a technicality, though.