I agree with your asessment that
Phyrexian Arena is too slow. You are spending three mana and need to untap twice with it to net a single card in advantage. Especially since the printing of
Prismatic Ending enchantments pretty much have lost their status as '*hard to interact' permanents in legacy. The same logic of course also applies to
Black Market Connection.
Gix, Yawgmoth Praetor has the upsides over
Phyrexian Arena of drawing a card the turn it entered the battlefield (if you already have a creature in play that can attack) and himself contributing a 3/3 body to the board. Though that second "upside" also means that he is even more unlikely to stick around as he also can be
Lightning Bolt'ed,
Swords to Plowshares'd etc.
I think when evaluating that card you can just ignore the second ability as the activation cost is way too high. I can see Gix more than arena, though I am still sceptical about it. Especially as you currently only have
Dauthi Voidwalker to play before it and trigger the draw.
Sign in Blood or
Night's Whisper I think are reasonable cards to be played maybe as a one or two of. You cannot afford to spend your early turns doing nothing and only want to topdeck them in the late game. Since
Sign in Blood has the marginal advantage of being a bad burn spell in addition to its normal card advantage mode, I would prefer that in your non-Wasteland version. However if you are utilizing colorless utility lands (and I absolutely think you should in your mono-color legacy deck), then I'd prefer
Night's Whisper as it is easier on your mana.
A buddy of mine plays
Castle Locthwain in his mono-black
Smallpox deck. A few games he actually did win off its back, but his deck is even more focused on resource denial than yours so it is more likely to go to a long game where it does matter. And even then it only was good in a few games. And in a format with
Wasteland,
Back to Basics,
Price of Progress etc you should really
consider if it is even better than a basic
Swamp.
Murderous Rider I think is a trap. Sure it is technically a two for one. But the 2/3
lifelink body will oftentimes be irrelevant. And when it isn't you will loose tempo again when it is removed after you have in all likelyhood already lost tempo when you spent three mana to remove a threat your opponent spent less mana on.
Liliana of the Veil is from all the cards you have mentioned my favorite. She is a powerful card that has an immediate impact on the board without needing other cards. In a similar vein
Liliana, the Last Hope could also be a consideration.
Dark Confidant is a classic black card advantage engine. True, you also need to untap with it, but at least it also attcks and is a mana cheaper than
Phyrexian Arena. And that is a lot in a format as fast as legacy. While your current mana curve maybe seems too high for Bob , he would also be another two-drop creature too make
Gix, Yawgmoth Praetor better in your deck.
My previously mentioned pox-buddy also runs two
Sedgemoor Witch'es. She is more cute than good. But I thought I'd tell you so you can decide if you want to try her.
Lastly you could also expand a bit on your Karn-package. Of course if you can assemble the combo the game is just over. But when you can't (or your opponent breaks it up) you really only have
Liquimetal Coating to get. Possible one-offs to get from the sideboard are: