Did Harry's original wand choose Harry based on the pair of them being the best match or could it have been influenced by the remnant of Riddle which was still inside Harry at that point?

 

So that you have an answer, yes and no.

Harry and Voldemort were similar from birth and became more and more tightly bound as their lives went on and it's all of this including, influenced by and more than the horcrux that gets Harry his wand.

If you look at the pottermore information on wandcores and woods however, you can see how dissimilar their wand woods are even though they share a Phoenix feather. Harry's wand wood was a poor match for the detachment of a Phoenix and reflects his personality in that it deals with his emotional and loving nature (from what I remember off the top of my head) whereas Voldemort's yew is different.

The wand chooses the wizard and it chooses and sees the entirety of the wizard. It's not a side-effect of the horcrux. It's everything Harry is and what he isn't.

 

Thinking about this, it occurs to me that the scar-crux might have been the reason all the other wands wanted nothing to do with him. His instincts were for good and the scar was radiating evil, so most wands would be saying 'You're freaking me out, lad'. If Harry had only been Harry, I could see any number of wands reacting favorably if not perfectly.

Then again, I think of wands as behaving like hunting dogs. Or Pokemon.

Aside from that, Harry having a Fate might have colored the perceptions of the wands. Assuming they could sense that, they'd all be saying 'Not me, mister,' in their own unique ways. Perhaps they even could sense that they'd be broken within seven years, and only the phoenix core had faith in destiny and no lingering fear of death to dissuade it.

In the end, it's how you see it and what you want to use as part of your story.

 

I think it would have been a good fit regardless. Unless one argues that the Horcrux warped Harry's personality (doubtful, given the whole super-duper capacity to love etc.), his sometimes rash, hot-tempered behaviour fits holly (according to Pottermore) which is also his Celtic wood to boot. Not sure whether that means much in canon.

Phoenix-feather cores are said to produce late-bloomer wands which eventually suit a wider breadth of magic than the others (again, re: Pottermore) and this does seem to reflect Harry's spikes of accomplishment in PoA, OotP and parts of DH.

 

If I remember right, and you're asking from aa strictly canon perspective, JKR hadn't yet come up with the idea of horcruxes when she wrote Philosopher's Stone. So it couldn't have.

However, from the long term perspective, maybe? It's whichever you want it to be I suppose.