I might be an odd duck who choose to stay in Tennoji with the JR Kansai Area Pass as it was simple to hop on the Airport Express to Kyoto or Yamatoji line to Nara. I wanted to stay in a place convenient for day trips and didn't mind having to hop on the subway to get to places in Osaka. The airport limo stop is Abenobashi. There's a Marriott in the Abeno Harukas super-skyscraper building (currently the tallest in Japan according to Wikipedia) but I stayed in Abeno Osaka Hotel Trusty across the street which should be in your budget. My visit was before Harukas was complete.