A solenoid has a core that moves when electrical current is applied.  The core physically comes in contact with the switch it actuates.  A relay is any device that can remotely activate a device based on an electrical signal.  All solenoids are relays but all relays are not solenoids.  You can call the thing on the starter and by the strut tower a relay, but you can only call the thing on the starter a solenoid.  Does that make sense? 
