Find & Replace/Formula Too Long

I have two different Find and Replace macros; both work, but both have issues.

I can't use Excel's normal Find/Replace because I get the error message "Formula too long"

This one works, but doesn't work consistently with large cells

Option Explicit

Sub ReplaceSomething()
   Dim sFind As String
   Dim sReplace As String
   sFind = InputBox("please enter what to find")
   sReplace = InputBox("Please enter what to replace with")
   If Len(sFind) > 0 Then
       Cells.Replace What:=sFind, Replacement:=sReplace, LookAt:=xlPart, _
                     SearchOrder:=xlByRows, MatchCase:=False, SearchFormat:=False, _
                     ReplaceFormat:=False
   End If
End Sub

For instance, my spreadsheet has cells containing thousands of characters. Sometimes this one will find and replace in those cells, sometimes it won't. Can't figure out why.

This one works perfectly, every time:

Sub ReplaceText()
    Dim c As Range

    For Each c In ActiveSheet.UsedRange
        c = Replace(c, "Dog", "Cat")
    Next
End Sub

What I'd like to do is take the Input box functionality from the first one and marry it to the consistent functionality of the second one. It seems like it would be easy, but I can't get it to work. I'd appreciate any help I can get.