The benchmark is flawed because the iterative version is doing too much work. Iterative BFS/DFS has an elegant simplicity once your get your mind wrapped around its core idea. Your implementation, by contrast, is fairly complex and, at least for me, unintuitive. The complexity comes from managing, mutating, and resetting the state variables, especially sequence and indices, as you go from level to level. Those repeated mutations slow things down.

Classic BFS/DFS. A typical implementation, by contrast, avoids the need to worry about resetting the status variables. Instead, it uses a queue/stack to hold independent copies of the state. The queue/stack functions as a TODO list. What goes into the TODO? The arguments that you would have passed recursively (there's a reason they call it a "call stack"). You must take care not to mutate those variables. Only the queue/stack is mutated.

def traverse_iterative(S, item):
    if S:
        # Initialize the TODO list.
        stack = [(S, [])]
        while stack:
            # Get the next data to check.
            xs, indices = stack.pop()
            for i, x in enumerate(xs):
                if x == item:
                    # Success.
                    return (indices + [i], len(indices))
                elif isinstance(x, (list, tuple)):
                    # Add it to the TODO list.
                    stack.append((x, indices + [i]))
    return ([], -1)

Benchmark. That function runs generally the same speed has your recursive function on my computer (0.152 vs 0.151, using your scenario). One could fuss around with details on both functions to squeeze out some more performance (for example, the edits shown below speed up the recursive function a small bit), but I'm mostly bored by that sort of thing.

Code review stuff. Your recursive implementation is reasonable and easy to understand. Just a few suggestions. (1) Define a failed search constant rather than hardcoding it in three places. (2) Iterate directly over Python collections, rather than iterating over the collection's indexes (and if you also need indexes, use enumerate). (3) Use isinstance() to check the type. (4) Very few Python programmers use for-else, because it's not intuitive (does "else" mean that the loop was broken or not, and are there any other tricky details I need to remember?), so just do the normal thing and put the failed return statement after the loop. And even if you find the for-else structure really handy in some circumstances (I never have), the current case isn't one them, because you never break the loop.

def traverse_recursive(S, item, indices=[]):
    FAIL = ([], -1)
    if S:
        for i, x in enumerate(S):
            if x == item:
                return (indices + [i], len(indices))
            elif isinstance(x, (list, tuple)):
                testCall = traverse_recursive(x, item, indices + [i])
                if testCall != FAIL:
                    return testCall
    return FAIL