Does anyone know where I can pick up one of the Legolas alternate art cards? It came in the Murder at the Prancing Pony Fellowship Deck, but not sure if the POD ones you can buy off the shelf have him or not? He's my favourite character and I love the art!

The PODs you can order after GenCon or the Fellowship event indeed do not include the alt art hero. Else there woudn't be such a high demand for them. Legolas should be relatively easy to find online, as there were a lot of copies of him made. Gimli is a lot more difficult to find, and a lot more expensive as well, since he was only released at GenCon.
I would suggest keeping an eye on Ebay for a copy, they usually sell there together with the POD scenario as well, and perhaps even the mat if you are lucky. Posting across other groups will help spread the word, allowing you to find a copy quicker. Good luck in your hunt!