Bisharp was one of the thoughts I had when I was saying it, but the problem is that it's not very easy to come by until pretty late in the game. The only way to get it (until you get to Route 4) is from the Growlithe Mystery Egg after the Police Officer Sidequest, which you obviously don't get much of a choice in. Other decent Dark types that are easier to get could be Umbreon (Eevee from Mysidia Railcave), Zoroark (quest started on the accessible roof in the Beryl Ward during a clear night), Honchkrow (Murkrow on a windy night in the Aqua hideout), Houndoom or Sharpedo (from your team leader after defeating the other team or in the other team's hideout), Scrafty (Scraggy from defeating the Pangoros in the Obsidia Slums), Malamar (Inkay from Byxbysion Wasteland Headbutt trees), Spiritomb (from Odd Keystone in Byxbysion Grotto), Krookodile (Sandile from Tanzan Mountain), Pangoro (Pancham from Obsidia Slums), or Crawdaunt (Corphish from Rock Smash on Apophyll Beach). Any of those would obviously cover your Psychic weakness, but some of them have a duplicate type too so it's up to you. Whichever you like best really.