Washington, DC: Duke Ellington
Texas: No one artist or act can really represent a state as large and diverse as Texas, but… Willie Nelson probably comes closest.
For other states, I might suggest the following guys as being iconic, even if some aren’t really from the state, and even if natives sometimes find the performer a bit embarrassing.
California: The Beach Boys (Even now, there are probably kids listening too BEach Boys songs and dreaming of hanging 10 on a beach in SOuthern Cal).
Colorado: John Denver (I know, he wasn’t really from Colorado, and many actual Coloradans wish he’d called himself John Atlanta, but I think this fits).
Hawaii: Don Ho, just ahead of Elvis himself
Indiana: John Cougar Mellencamp?
Louisiana: Louis Armstrong? Al Hirt?
Michigan: Loads of great acts, but how many make you think of Michigan or even Detroit? I’d say… Bob Seger?
Minnesota: Dylan was from Minnesota, but didn’t represent it. I’d vote for Prince. Before Prince, who even knew Minneapolis HAd a music scene?
New Jersey: Tie between Frank SInatra and Bruce Springsteen
Oklahoma: Woody Guthrie?
Utah: The Osmonds?
Washington: Nirvana
Thing is, even genuinely iconic artists aren’t necessarily identified with any given state. Hank Williams was an icon from Alabama, but do people really remember him as an Alabama boy? I don’t think so.
That’s a good point. Even with Billy Joel, though, I think “NYC.” It would be hard to find a person who’s the quintessential of the whole state because the culture changes dramatically depending on what region you’re in. New York: FDR or New York: Teddy Roosevelt could work.
Also, for Massachusetts, JFK might be a good choice.
Ohio - The Wright Brothers-first to build a 3 axis controlled powered airplane (OK, technically Wilbur was born in Indiana), John Glenn first- American astronaut to orbit the Earth, Neil Armstrong-first man on the moon, Thomas Edison-inventor of stuff.
CA:
Jerry Garcia
(to help out the upstate NY’er’s: ) Pete Seeger
IN: R. Dean Taylor (look it up!)
That’s who I thought of.
Virginia: George Washington.
They don’t get much more iconic than that.
The Beach Boys are a good choice for California I guess, but I nominate Huell Howser instead.
Commenting on other states: agree that Lincoln and Springsteen are slamdunks for Illinois and New Jersey, respectively. I’d have to say the Wright Brothers are more strongly identified with Ohio than either Glenn or Armstrong, even if they did fly considerably higher. And Mellencamp with Indiana, for sure.
Georgia: William Tecumseh Sherman. Burning down the house! 
I’d call it tie: Washington/Lee
In pretty much any other universe, Robert Edward Lee would have been a national hero.
But, for a cause died a-bornin’…
Maryland: either Cal Ripken Jr., Johnny Unitas, or Brooks Robinson.
The pickings are really pretty slim here in the state where I’ve been sojourning for the past 15+ years. Politically, there isn’t much other than Lord Baltimore (17th century) and Spiro Agnew (ack!). Music? Francis Scott Key, and nobody much before or since. Sports? The Babe started off here, but his primary identification in people’s minds is as a New York Yankee, and that’s as it should be.
So Cal Jr., Johnny U., or Brooksie. Take your pick.
Nah.
Fifty years ago, or even twenty, I’d have said you were right. But especially since the dawn of the Internet era, the Lost Cause has lost a lot of its cachet, thank goodness, as it has become harder for even its most stalwart defenders to avoid the truth that secession was almost entirely about slavery. It was a lot more possible before then to snow people with a less-than-factual version of what the Confederacy was about, and to sell it as something noble and romantic. And even to convince people that with respect to slavery, Lee had no dog in that fight, or at least was the sort of slaveowner who treated his human property in an honorable way.
So Lee’s pedestal isn’t as high as it once was. And even in a state with Thomas Jefferson, James Madison, James Monroe, and Patrick Henry as native sons, George Washington still dominates.
I am not from Alabama (and have never even been there) but I would have thought Lynyrd Skynyrd the obvious choice.
I am British, so I say The Beatles. I also lived in California for a long time, for which I think The Beach Boys are probably the best answer.
I am going on the assumption that the OP intended this to be about musicians.
I assumed that if the OP wanted this to be about musicians, the OP would have posted the thread in Cafe Society.
And, and least to me, Elvis is not someone you bring up when you want an example of a musician; he’s someone you bring up when you want an example of a Celebrity Icon.
Lynyrd Skynyrd is from Florida.
In terms of iconic figures from Alabama, it would probably have to be Paul “Bear” Bryant.
Come on, it’s Sarah Palin!
I’d say Bear Bryant and George Wallace are a tie.
Does Maine have anyone more iconic than Stephen King?
I suppose Benjamin Franklin stands alone as an icon of Pennsylvania, doesn’t he? (Even though he was originally from Massachusetts).
In terms of recognition by most people not from the state, it’s going to be hard to top Bryant and Wallace. Between the two my vote would go to Bryant.
I have looked at every name on this list and even though I think some of them might compete for notoriety or fame, it’s hard to place anybody above those two. Jimmy Buffett, anyone? 