C — как сделать замену подстроки в строке (руками)?
А что делает startsof()?

Даже если принять, что оно действительно ищет вхождение второй строки в первой - у вас там в каждой второй строчке ошибка.

malloc(string_size + sub_size - to_size);

Объясните мне, как вы получили вот это значение длины?

А дальше копирование у вас неправильно. Чтобы заменить строку-вхождение вам надо в ответ скопировать начало str1 до вхождения, потом скопировать to, потом скопироваать конец строки str1, после вхождения. Это должны быть три параллельных цикла. У вас в одной ветке их 2 (один в функцию бесполезную спрятан), в другой - только 1.
1. Не правильно вычисляете размер будущей строки в первом случае. В первом случае результирующая строка будет меньше оригинальной, у вас же получается больше.
2. Не выделяете место под завершающий нулевой символ. Вообще завершающий ноль вы полностью игнорируете. Без него у вас в итоге получится не строка, а массив символов. Раз уж вы делаете все в ручную, то и завершающий ноль надо проставлять руками.
3. Согласен с Wataru на счет startsof и трех циклов.
4. Я бы сначала искал вхождение строки замены и только если оно найдено производил бы необходимые действия, в т.ч. и выделение памяти под новую строку. У вас же сейчас предполагается, что подстрока замены всегда найдется, что в общем случае не верно. 
5. Что будете возвращать, если замены не будет? Будете просто выделять память под новую строку и возвращать новую строку аналогичную оригинальной? Или будете возвращать указатель оригинальной строки? Но тогда будет мешать квалификатор const для str1. А кроме того, если возвращать указатель на оригинальную строку, то что должен делать вызывающий код со старой строкой? Т.е. если замена была, то вы возвращаете новую строку и в вызывающем коде старую строку можно удалить. А если строка не найдена, то старую строку удалить нельзя, т.к. вы вернули указатель на нее же. В общем надо еще продумать как возвращать результат. Я бы на самом деле возвращал признак была замена или нет (или количество замен), а результирующий указатель надо возвращать в дополнительном параметре. Если замен нет, то либо указатель не возвращается, либо возвращается указатель на str1.
6. в качестве оптимизации:
for (int i = 0; i < strlength(str1); i++)
Вызываете на каждой итерации strlength.