Q:

Возникает исключение при десериализации

Сериализуемый класс:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Server
{
    [Serializable]
    class Song
    {
        public int songID { get; set; }
        public string songName { get; set; }
        public string songArtist { get; set; }
        public string songAlbum { get; set; }
        public string songYear { get; set; }
        public byte[] songPicture { get; set; }
        public Song(int _songID, string _songName, string _songArtist, string _songAlbum, string _songYear)
        {
            songID = _songID;
            songName = _songName;
            songArtist = _songArtist;
            songAlbum = _songAlbum;
            songYear = _songYear;
        }
    }
}

Передаю с сервера клиенту
Song thisSong = new Song(0, "HEYHEYHEYHEYHEYHEY", null, null, "nothing"); 
formatter.Serialize(stream, thisSong);

Принимаю на клиенте
do
{
     song = formatter.Deserialize(stream) as Song;
} while (stream.DataAvailable);

При отладке выяснил, что stream.DataAvailable = true
Не могу понять чем вызвана проблема, это исключение выплывает на клиенте

A:

У вас типы Song на сервере и на клиенте - разные. Напомню, что в "самое полное" имя типа входит имя сборки, именно оно-то и отличается. Потому-то при десериализации клиент и начинает искать серверную сборку.
Выделите тип Song и другие подобные ему в отдельную библиотеку, общую для клиента и сервера.
А еще лучше - перейдите на другие методы сериализации. Самый простой вариант -  используйте [DataContract] и DataContractSerializer

