South - Where to go w/ my free tix?

I won two round trip tickets on Seaport Airlines that I need to use before 3/1. I'm based out of MCI, so the only appealing destination looks like MEM (although I only have first-hand knowledge of HRO among their other southern destinations). I think a couple days on Beale Street with the wife sounds appealing, and maybe checking out some of Memphis's other tourist attractions, I've never seen Graceland... I'm still open to HOT, JBR, ELD, or SLN, but really leaning towards MEM.

I've only every passed through Memphis, never spent much time in the city. Would a rental car be recommended? or should I rely on ground transportation to a Beale St area hotel? Thanks in advance for the info!