Normally, quantifiers in sed are greedy, which is why you will always match the last =. What defines the first = is that all the characters before it are not =, so:
sed 's/^[^=]*=//'
Your question implies that either : or = are valid markers, in which case
sed 's/^[^=:]*[=:]//'