Lexi it's funny you're moving out of dance\electronic music genre because that's the general direction I'm moving towards. I know what you mean when you say you yearn for something else and I realise you don't just want names of artists, you want specific songs.
Without further ado, here's my recommendations:-
Rock:
The B-52s - Roam
The Pixies - Debaser
The Psychedelic Furs - Sister Europe
Magnapop - Slowly Slowly
The Cult - She Sells Sanctuary
David Bowie - Cracked Actor
Public Image Ltd - Public Image Limited
The La's - Looking Glass
Florence and the Machine - Dog Days are Over
Interpol - PDA
Sarah McLachlan - Adia
Steve Earle - I Feel Alright
Sinead O' Connor - Mandika
Marc Bolan - King of the Rumbling Spires (Rare version on youtube)
Haircut 100 - Love Plus One
Soundgarden - The Day I tried to Live
The Cocteau Twins - Wax and Wane
R.E.M. - Superman
The Lemonheads - If I could talk I'd tell you
R&B\Soul:
The Brother's Johnson - Strawberry Letter 23
Mavis Staples - I'll Take You There
Erykah Badu - Telephone (Louie Vega remix)
Sergio Mendes feat. Ledisi - Waters of March (DJ Spinna vocal)
Roy Ayers - Everybody Loves the Sunshine
Amerie - Talkin About
Otis Redding - Hard to Handle
Cajmere feat. Dajae - Brighter Days (original mix)
Stevie Wonder - Sunset
Mavis Staples - A Piece of the Action
Amerie - Why Don't We Fall in Love (Richcraft remix)
Nuyorican Soul - I am the Black Gold of the Sun
Sade - Couldn't Love you More (Rare House Mix)
Hip Hop\Rap:
De La Soul - Eye Know
Joey Badass - Waves
A Tribe Called Quest - Electric Relaxation
N.E.R.D. Everyone Nose
Nas - New York State of Mind
Kendrick Lemar - Swimming Pool
Goldie feat. KRS One - Digital
Busta Rhymes - Everything Remains Raw
ODB - Got Your Money
Azealia Banks - Slow Hands (Interpol Cover)
Mos Def - Mathematics
Beastie Boys - No Sleep til Brooklyn
Closest I get to Reggae is Jungle or Bob Marley.
I think you would know all of my pop recommendations so I won't list them.
Hope you enjoy