Cool. Thanks for replying with more info
First up, I do agree with BoardSys that upgrading your front 3 speakers would also be a big improvement. Speakers and subwoofers make, by far, the greatest difference in the sound you hear. So if you're wanting to upgrade, those are where you should focus your money first.
I would still focus on the subwoofer as the top priority though. If there's room left in the budget after getting a great sub to also upgrade your speakers, then that's great! But I would prioritize personally and focus on the subwoofer first and foremost. The Infinity speakers that BoredSys suggested are indeed quite good. But they are still inexpensive speakers. They hit above their price point, so they're a great value. But they're certainly not the last word in speaker sound quality or anything. My point is that you might want to save up a bit more and purchase speakers that are even better than the Infinity speakers when you upgrade your Polks. Totally up to you. But if you're generally happy with your Polk speakers for now, it's sort of a "you don't know what you're missing" situation, so it's just my opinion that I'd probably want to aim a little bit higher for a speaker upgrade. Maybe something like EMP Tek's speakers, which are at a very reasonable price point and absolutely gorgeous to look at. Great sound from EMP's RBH parent company
Anyways, there's no disagreement when it comes to recommending that a new subwoofer would be a great way to upgrade your system! Trust me, compared to your Polk sub, a new subwoofer is going to make a very, very noticeable improvement
Since your theater area open completely into another adjacent room, you have to consider your theater room to be the entire space, not just the 15' x 15' theater area. A subwoofer doesn't "know" where your theater area ends and your living room area begins. It just "sees" the entire open space and tries to pressurize it and fill it with bass.
So in terms of just cubic footage that you need to pressurize, you're likely into "large" room territory - that would be anything over 3000 cubic feet, which you more than likely have with your theater area and adjoining living room. Since you mostly care about one, prime, "sweet spot" seat, you will probably be ok with just using one subwoofer. In a large room, the Rythmik FV12 that we've mentioned might have some trouble hitting loud, close-to-reference type levels. It's an excellent $500 sub, but there's only so much that a 12" driver and a 300 Watt amp can do!

That said, it doesn't sound as though you really crank your movies and music to full 100dB + reference levels. But then again, you enjoy action movies and rock music, so some good output and deep extension is called for here.
I would say that a pair of FV12 at $1000 + shipping would almost certainly do well for you if you want to go the dual subwoofer route. Since you said that you have pretty good freedom to place your subwoofers where you like, you'd be able to take advantage of dual subs to get more even and linear frequency response throughout your entire room. Fewer big peaks and valleys is always a nice thing to have
I wouldn't go for any sub less expensive than the $500 Rythmik FV12 in your case. In my experience, the FV12 is a subwoofer that "moves the goal posts" for what a $500 sub can do. Below that, you're definitely into obvious compromise territory, where you're either giving up deep bass extension, or giving up tight transient response and accuracy. The FV12 is the least expensive subwoofer out there that really delivers nicely in both areas, which is why I end up recommending it so often.
THAT SAID - as I mentioned, the FV12 might not have enough sheer output for your room size. A pair of them would likely be fine, but if you want to go with a lone sub, I would recommend that you aim higher than the FV12. Going for something a little bit more expensive than the FV12 also gives you some small, but still noteable improvements in terms of extension and overall sound quality in addition to obviously more output. The FV12 is great and a really huge step up over anything beneath it. But that doesn't mean you can't do even better if you spend a bit more
One sub that I would strongly consider for your setup would be the SVSound PB12-NSD DSP box or PC12-NSD DSP cylinder. They're very close in price ($770 for the box; $750 for the cylinder) and those prices include shipping, so it's really just a matter of what form factor you prefer. The cylinder is great if you want to save on floor space. It's only about 16" in diameter, so it's really easy to place so long as you're ok with a tall, black tube

The box version is pretty big. I should mention, with any of these subs that we recommend, make sure that you look at the dimensions and really understand how large they are! Compared to your PSW10 sub, these might look like monsters!
Anyways, at this $750-ish price point, the SVSound NSD subs dig right down to 20Hz with authority and should have no problem at all with your room size. What's great about both Rythmik's and SVSound's subs is that they're basically unbreakable. The excellent engineering that goes into both brands means that the best filters, compressors and processing are used to make sure that even if you crank the volume way up past where the subwoofers can actually go, the subs just keep it all under control, play as loudly as they can without distortion or damage, but never get into any sort of "danger" zone.
The other subs I would strongly consider would be the HSU Research VTF-3 MK4 and the Outlaw Audio LFM-1 EX. Again, these are physically large subs, so make sure you're aware of their dimensions. To be as honest as possible, the SVSound NSD subs can outdo these two when it comes to sheer, maximum really deep bass output. But it's not a huge margin. The NSD subs have just a tiny bit of overhang. I'm really splitting hairs here, but what I'm saying is that some subs do sound just a little bit "tighter" than the SVS NSD subs. The NSD subs are good, don't get me wrong. But there's a bit of room for improvement in the transient response. The HSU VTF-3 MK4 is a great sub for a large room for both music and movies. HSU's subs have a really nice sound quality to them when it comes to transient response and just the tightness and clarity of the bass. Dr. Hsu is also involved in the design of Outlaw's subs, so they're sort of "related" in that way. The LFM-1 EX is like a close cousin to the VTF-3 MK4. You can check out Audioholics' excellent review of the Outlaw LFM-1 EX to get a good idea of how it performs and expect something pretty close from the VTF-3 MK4, although the VTF-3 MK4 might even be a hair better
That should about do it! To get something better than any of those subs, you have to go over your $1000 budget and the subs start to get physically huge too

To be honest, I don't think you could go "wrong" with any of these subs. They'd all be an absolutely massive step up over your Polk PSW10 sub!
Hope that helps. And enjoy you big upgrade!