What should he upgrade first?
Chrysaoras. They do 2 more damage, which is great.
2. Any suggestions for what he should put in?
3. Should he take anything out?
You want to ultimately end up with a 30 card deck, because those are the fastest and smoothest. So:
+1 Chrysaora
+1 Poison (The theme of this deck is Poison, so you should concentrate on it)
+2 Bonewall (More useful than Boneyard, especially because because you already have Aflatoxin)
-3 Photon (You can always use Aflatoxin on Chrysaoras)
-2 Boneyard
-1 Plague
-1 Bone Pillar
That will give you 30 cards.
What should his rare weapon be for his 500 point quest? (Both him and me are pointing toward Arsenic, but we don't know yet.)
Hm. Later on, you'll want to build a False God deck in which a Pulverizer and an Eternity are key to. I'd suggest taking either one of these. The Arsenic is useful but not necessary to this deck; one of these False God rare weapons would be more useful in the long term.