Andya: From the sound of it, I'm pretty sure your "evolutionist" is proposing the old idea (originally put forward by Lamarck
) that evolution consists of a change from the simple to the complex, from the lower to the higher. IOW, directed evolution - a change toward ever increasing perfection.
Gould was absolutely correct: the modern science of evolutionary biology has pretty much cleaned the clock of this old idea. Since evolution (as we understand it today) is actually just the change in the properties of populations of organisms over time, there is no requirement toward "increasing perfection". There are quite a few examples from nature that would appear to be arguing that some organisms have actually "decreased complexity" over the course of evolutionary history. Snakes losing their legs (evidenced by the vestigial pelvus in certain species of boa), eukaryote cellular organelles formed from originally free-living bacteria which have lost their ability to survive outside the cell as well as many of their original structures, certain virii, etc, are all examples of organisms that have "lost" functions/structures over time as they adapted to their environments. I'm sure you can come up with other examples.
If you'd like to get more info on which particular flavor of this fallacy your opponent is proposing (Bauer's orthogenesis, Haeckel's "ontogeny recapitulates phylogeny", etc), I can try and provide more direct refutations.
Hope this helps.