The problem is because of removing the words from the ArrayList, words. Remove the line, words.remove(words.get(i)) to get the desired output.

Do it as follows:

import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>(
                Arrays.asList("Canivete", "Almofada", "Corda", "Parede", "Caixa", "Zilhão", "Dedo"));
        ArrayList abc = new ArrayList<>();
        ArrayList rest = new ArrayList<>();

        for (int i = 0; i < words.size(); i++) {
            char firstChar = words.get(i).charAt(0);
            if (firstChar == 'A' || firstChar == 'B' || firstChar == 'C') {
                abc.add(words.get(i));
            } else {
                rest.add(words.get(i));
            }
        }
        System.out.println("Start with A,B or C: " + abc);
        System.out.println("Start with other letters: " + rest);
        System.out.println("Original array: " + words);
    }
}

Using Stream API:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> words = new ArrayList<>(
                Arrays.asList("Canivete", "Almofada", "Corda", "Parede", "Caixa", "Zilhão", "Dedo"));
        List<String> abc = words.stream().filter(s -> s.startsWith("A") || s.startsWith("B") || s.startsWith("C"))
                .collect(Collectors.toList());
        List<String> rest = words.stream().filter(s -> !(s.startsWith("A") || s.startsWith("B") || s.startsWith("C")))
                .collect(Collectors.toList());
        System.out.println("Start with A,B or C: " + abc);
        System.out.println("Start with other letters: " + rest);
        System.out.println("Original array: " + words);
    }
}

Output:

Start with A,B or C: [Canivete, Almofada, Corda, Caixa]
Start with other letters: [Parede, Zilhão, Dedo]
Original array: [Canivete, Almofada, Corda, Parede, Caixa, Zilhão, Dedo]

Once an element is removed from the ArrayList, all the elements to the right of the removed element shift to the left of one.

E.g. if you have an ArrayList A = [1, 2, 3, 4] and do A.remove(0) then the result ArrayList will NOT be A = [null, 2, 3, 4] but it will be A = [1, 2, 4].

The problem with your program lies in the failure to handle this behavior of the remove() function.

How can you handle it?

Just change the exit condition of the for-loop. Always check the first element, in your case, and exit when the ArrayList has been emptied then words.size() == 0. You don't need to increment i.

Solution

public static void main(String[] args) {
    //arraylist pra verificar quais strings começam com a,b,c
    ArrayList<String> words = new ArrayList<>(
            Arrays.asList(
                    "Canivete",
                    "Almofada",
                    "Corda",
                    "Parede",
                    "Caixa",
                    "Zilhão",
                    "Dedo"
            ));

    System.out.println("Original array: " + words + "\n");

    ArrayList<String> abc = new ArrayList<>();
    ArrayList<String> rest = new ArrayList<>();

    for (int i = 0; words.size() > 0;) {
        char firstChar = words.get(i).charAt(0);
        if (firstChar == 'A' || firstChar == 'B' || firstChar == 'C') {
            abc.add(words.get(i));
        } else {
            rest.add(words.get(i));
        }
        words.remove(words.get(i));
    }
    System.out.println("Start with A,B or C: " + abc);
    System.out.println("Start with other letters: " + rest);
}

Another problem is when you try to print the original ArrayList at the end of the program. Careful!

The ArrayList words has been emptied so you will print an empty ArrayList. For this you can print it at the beginning or do something else.

Sample Output

Original array: [Canivete, Almofada, Corda, Parede, Caixa, Zilhão, Dedo]

Start with A,B or C: [Canivete, Almofada, Corda, Caixa]
Start with other letters: [Parede, Zilhão, Dedo]

Your issue is with your for loop. You are incrementing the index 'i' on each iteration of the loop, then removing the word at words(i). Because i gets incremented, but the size of the words list is reduced each iteration, 'i' quickly increases to the new size of the words list without actually evaluating the Strings at the end.

To correct, you simply need to avoid incrementing i on each iteration:

for(int i = 0; i < words.size();){ //Notice i is not being incremented (i++)
    char firstChar = words.get(i).charAt(0);
    if(firstChar == 'A'||firstChar == 'B'||firstChar == 'C'){
        abc.add(words.get(i));
    }else{
        rest.add(words.get(i));
    }
    words.remove(words.get(i));
}